Kth largest element in an array
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
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];}