215. Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in sorted order (not the kth distinct element). Try to solve it without sorting.

The kth largest sits at index n − k in sorted order. Partition around a pivot like quicksort, then continue only in the side that contains that index.

1function findKthLargest(nums: number[], k: number): number {
2  const target = nums.length - k;
3  let lo = 0, hi = nums.length - 1;
4  while (true) {
5    const pivot = nums[hi];
6    let p = lo;
7    for (let i = lo; i < hi; i++)
8      if (nums[i] <= pivot) { [nums[i], nums[p]] = [nums[p], nums[i]]; p++; }
9    [nums[p], nums[hi]] = [nums[hi], nums[p]];
10    if (p === target) return nums[p];
11    if (p < target) lo = p + 1;
12    else hi = p - 1;
13  }
14}

target = 4pivot = 4

nums

target

Sorted, the answer is at index 4.

1 / 0

Space: play/pause · ←/→: step