Kth Largest Element in an Array: A Size-K Min-Heap
Find the kth largest array element with a size-k min-heap: JavaScript code, invariant, walkthrough, complexity, and common mistakes.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Finding the kth largest value is not the same job as sorting an array, even though sorting can answer it. If all we need is one rank, ordering every pair of values is often extra work. The useful question is: which values must still be allowed to compete for the top k positions?
The visualizer answers that question with a min-priority queue capped at k values. It scans the array once, admits each number temporarily, and immediately evicts the smallest whenever the queue overflows. By the end, the queue contains the k largest values in the input. Its minimum is therefore the kth largest value overall.
The problem
Given an unsorted integer array nums and an integer k, return the kth largest element. This is a rank among elements, not among distinct values: duplicates occupy separate positions.
Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Sorted descending: [6, 5, 4, 3, 2, 1]For example, [1, 1, 1, 2, 2, 2, 3, 3, 3] with k = 4 returns 2. The three 3s fill ranks one through three, and a 2 fills rank four. Do not remove duplicates unless the problem explicitly asks for a distinct rank.
Start with the straightforward baseline
The simplest solution copies and sorts the whole array in descending order, then returns sorted[k - 1]. Its time cost is O(n log n), and it may mutate the original array if sorting happens in place.
That is a perfectly reasonable choice when the full sorted order is needed later. It is less attractive when k is small and the only requested result is one boundary value. A size-k heap does not need to preserve the order among the winners; it only needs to reject values that cannot finish in the top k.
Quickselect is another valid alternative. It partitions around pivots and has expected O(n) time with O(1) auxiliary space, but can degrade to O(n²) with unlucky pivots and is more intricate to implement correctly. The visualizer deliberately teaches the bounded heap because its invariant is easy to inspect and it generalizes directly to streaming data.
The key invariant: keep exactly the current top k
Use a min-heap, not a max-heap. After processing any prefix of the array, maintain this invariant:
The heap contains the largest
min(k, number of processed values)elements from that prefix. When it haskelements, its root is the smallest of those winners.
For every number:
- Enqueue it in the min-heap.
- If the heap now has more than
kelements, dequeue the root. - After the scan, return the root.
Why is removing the minimum safe? An overflow heap has k + 1 candidates. Its minimum has at least k elements in that heap that are greater than or equal to it, so it cannot be in the final top k for the prefix. Removing it restores the invariant. Future values can displace current winners, but they can never make an already discarded smaller value necessary again.
A max-heap exposes the largest value, which is the opposite end from the one we need to discard on overflow. You could put every number in a max-heap and pop k - 1 times, but that takes O(n + k log n) and stores all n values. The bounded min-heap stores only k.
JavaScript solution
The visualizer's canonical solution uses a MinPriorityQueue. Exact API names can differ by package; the important operations are insert, remove-min, size, and peek-min.
var findKthLargest = function(nums, k) {
const pq = new MinPriorityQueue();
for (let i = 0; i < nums.length; i++) {
pq.enqueue(nums[i]);
if (pq.size() > k) {
pq.dequeue();
}
}
return pq.front();
};The queue is a binary heap, not a sorted array. Its only required order is that each parent is no greater than either child, so the root is always the minimum. A push or dequeue repairs that local heap property in O(log k) time.
Walkthrough: [3, 2, 1, 5, 6, 4], k = 2
The heap rows below are shown sorted for readability. A real binary heap may have a different internal array arrangement while retaining the same root.
| Number | Heap after insert | Overflow action | Retained top-two candidates |
|---|---|---|---|
3 | [3] | Keep | 3 |
2 | [2, 3] | Keep | 3, 2 |
1 | [1, 2, 3] | Remove 1 | 3, 2 |
5 | [2, 3, 5] | Remove 2 | 5, 3 |
6 | [3, 5, 6] | Remove 3 | 6, 5 |
4 | [4, 5, 6] | Remove 4 | 6, 5 |
The final heap contains 5 and 6. Its root is 5, the smaller of the two largest values, so it is the second largest element.
Notice the last operation: 4 gets inserted even though it is not a winner. The uniform push-then-trim rule is easy to prove and avoids a separate comparison branch. An optimized implementation may compare against the root first when the heap is full, but it must preserve the same invariant and handle duplicates correctly.
Why the root is the answer
When the heap holds k values, every discarded value is less than or equal to the root that discarded it at that time. The heap's members are exactly the largest k values seen. Among those k members, the root is the smallest. There are therefore k - 1 retained values greater than or equal to it, and all non-retained values are no larger than the cutoff. That is precisely the definition of kth largest.
This argument also handles equal values. If several values equal the root, any one of them can occupy the heap root; ranks count occurrences, and no stable tie order is needed.
Complexity and trade-offs
| Strategy | Time | Extra space | Best fit |
|---|---|---|---|
| Full sort | O(n log n) | O(1) to O(n) | You also need the ordering |
Size-k min-heap | O(n log k) | O(k) | k is small or data is incremental |
| Quickselect | O(n) expected, O(n²) worst | O(1) | One-shot selection with careful partitioning |
Each of n values enters the heap and may cause one removal. The heap never exceeds k + 1 during an iteration, so both operations cost O(log k). For k = 1, this reduces to tracking the maximum in O(n) time and O(1) heap space. For k = n, the heap grows to all elements and the complexity becomes O(n log n), so sorting is often simpler.
Common mistakes
- Using a max-heap and removing its root on overflow. That throws away the largest candidate instead of the smallest.
- Returning
kas a zero-based index. The rank is one-based:k = 1means the maximum. - Deduplicating the input. Repeated values count as repeated ranks.
- Claiming the heap array is sorted. Only the root relation is guaranteed.
- Forgetting to validate
1 <= k <= nums.lengthin a production-facing API.
Where to go next
The same cutoff idea powers the online version, where values arrive after initialization and the answer must be returned after each insertion. Read Kth Largest Element in a Stream next, or review Min-Heap Operations to see the sift-up and sift-down mechanics beneath priority queue methods.
Step through Kth Largest Element in an Array interactively to watch each insertion, overflow check, and root eviction.
FAQ
Why is a min-heap used to find a largest element?
The heap holds only the k largest candidates, so the value that should be easiest to remove is the smallest among them. A min-heap places that cutoff at the root. Once processing finishes, the cutoff is the kth largest value.
Can I use Quickselect instead?
Yes. Quickselect is expected O(n) for a one-time query and is often excellent in interviews. Its worst case is O(n²), it commonly mutates the input, and it does not naturally support ongoing insertions. The size-k heap has a predictable O(n log k) bound and reuses the same idea for streams.
What happens when k is 1 or equals the array length?
For k = 1, every smaller candidate is evicted and the root is the maximum. For k = nums.length, nothing overflows and the root becomes the minimum, which is the nth largest element.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.