Kth largest element in an array

Medium

Problem

Return the kth largest element of an unsorted array — by sorted position, not the kth distinct value.

Example 1

Input:  nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5

Example 2

Input:  nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4

Test cases

Case 1

Input:    [3,2,1,5,6,4], 2
Expected: 5

Case 2

Input:    [3,2,3,1,2,4,5,5,6], 4
Expected: 4

Case 3

Input:    [1], 1
Expected: 1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Min-heap of size k

Time O(n log k)Space O(k)

Keep the k largest so far; the heap root is the kth largest. Great for a stream.

class MinHeap {
constructor() { this.a = []; }
get size() { return this.a.length; }
peek() { return this.a[0]; }
push(x) { const a = this.a; a.push(x); let i = a.length - 1;
while (i && a[(i - 1) >> 1] > a[i]) { [a[(i - 1) >> 1], a[i]] = [a[i], a[(i - 1) >> 1]]; i = (i - 1) >> 1; } }
pop() { const a = this.a, top = a[0], last = a.pop();
if (a.length) { a[0] = last; let i = 0;
for (;;) { let s = i, l = 2*i+1, r = 2*i+2;
if (l < a.length && a[l] < a[s]) s = l;
if (r < a.length && a[r] < a[s]) s = r;
if (s === i) break; [a[s], a[i]] = [a[i], a[s]]; i = s; } }
return top; }
}
function findKthLargest(nums, k) {
const h = new MinHeap();
for (const x of nums) { h.push(x); if (h.size > k) h.pop(); }
return h.peek();
}

2. Quickselect

Time O(n) avgSpace O(1)

Partition for the (n−k)th smallest index. Average O(n), no extra structure.

function findKthLargest(nums, k) {
const target = nums.length - k;
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const pivot = nums[hi];
let i = lo;
for (let j = lo; j < hi; j++) if (nums[j] < pivot) [nums[i], nums[j]] = [nums[j], nums[i]], i++;
[nums[i], nums[hi]] = [nums[hi], nums[i]];
if (i === target) return nums[i];
i < target ? (lo = i + 1) : (hi = i - 1);
}
return nums[lo];
}