FAANGPrep Sprint
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
k = 2 · THE ROOT IS THE 2ND LARGEST SO FAR
EMPTY HEAP
nums
empty heap
heap array · at most k = 2
Size
0/2
Root
—
Answer
—
An empty min-heap. It will never keep more than k = 2 values
Next
Read nums[0] = 3
nums
k
Legend & Complexity
The number read, or the value moving in the heap
The parent or child it was swapped with
The minimum popped: too small to be in the top k
The root at the end: the kth largest
Time
O(n log k)
Space
O(k)
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};