Kth Largest Element in an Array
Find the kth largest element in an unsorted array.
Problem Understanding
Return the value that would sit at position k if the integer array nums were sorted from largest to smallest.
Duplicates count separately: in [3,3,2] the 2nd largest is 3, not 2.
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
Algorithm Strategy
We can use a Min-Heap to efficiently find the Kth largest element.
- Initialize a Min-Heap: We will maintain a heap of size
k. - Iterate through the array: For each number:
- Push it onto the heap.
- If the heap size exceeds
k, pop the smallest element (root).
- Result: After processing all numbers, the heap contains the
klargest elements. The smallest of these (the root) is exactly thekth largest element.
Why Min-Heap?
We want to keep the "largest" elements. By popping the smallest element whenever we exceed size K, we discard the "small" numbers and keep the "large" ones.
Interactive Visualization
Push each number onto a min-heap and pop whenever it holds more than k. The tree and its array are the same heap; the root at the end is the kth largest.
Dry Run
Input: nums = [3, 2, 1, 5, 6, 4], k = 2
| Step | Num | Action | Heap | Size | Comment |
|---|---|---|---|---|---|
| 1 | 3 | Push 3 | [3] |
1 | |
| 2 | 2 | Push 2 | [2, 3] |
2 | Min-Heap property (2 < 3) |
| 3 | 1 | Push 1 | [1, 3, 2] |
3 | Size > k (3 > 2), Pop Min (1) |
| 4 | - | Pop 1 | [2, 3] |
2 | Heap holds largest so far |
| 5 | 5 | Push 5 | [2, 3, 5] |
3 | Size > k, Pop Min (2) |
| 6 | - | Pop 2 | [3, 5] |
2 | |
| 7 | 6 | Push 6 | [3, 5, 6] |
3 | Size > k, Pop Min (3) |
| 8 | - | Pop 3 | [5, 6] |
2 | |
| 9 | 4 | Push 4 | [4, 6, 5] |
3 | Size > k, Pop Min (4) |
| 10 | - | Pop 4 | [5, 6] |
2 | |
| End | - | Root is Ans | 5 |
- | 5 is the 2nd largest |
Edge Cases
- k = 1: the heap keeps one value, the maximum.
- k = n: nothing is ever popped, and the root is the minimum.
- Duplicates: each copy counts. In
[3, 2, 3, 1, 2, 4, 5, 5, 6]withk = 4the answer is 4 — both 5s take a place. - Negative numbers: nothing changes; the heap compares values, not magnitudes.
Solution
A min-heap of size k in every language. JavaScript, TypeScript and C have no built-in heap, so their tabs carry a small one.
Kth Largest Element in an Array Code
1class Heap {2 constructor(before) {3 this.items = [];4 this.before = before;5 }67 size() {8 return this.items.length;9 }1011 peek() {12 return this.items[0];13 }1415 push(item) {16 const a = this.items;17 a.push(item);18 let i = a.length - 1;19 while (i > 0 && this.before(a[i], a[(i - 1) >> 1])) {20 const parent = (i - 1) >> 1;21 [a[i], a[parent]] = [a[parent], a[i]];22 i = parent;23 }24 }2526 pop() {27 const a = this.items;28 const top = a[0];29 const last = a.pop();30 if (a.length > 0) {31 a[0] = last;32 let i = 0;33 while (true) {34 const left = 2 * i + 1, right = 2 * i + 2;35 let first = i;36 if (left < a.length && this.before(a[left], a[first])) first = left;37 if (right < a.length && this.before(a[right], a[first])) first = right;38 if (first === i) break;39 [a[i], a[first]] = [a[first], a[i]];40 i = first;41 }42 }43 return top;44 }45}4647var findKthLargest = function(nums, k) {48 const heap = new Heap((a, b) => a < b);49 for (const num of nums) {50 heap.push(num);51 if (heap.size() > k) {52 heap.pop();53 }54 }55 return heap.peek();56};