#703
Kth Largest Element in a Stream
Easy Min-heap of size k
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Design a class that receives numbers one by one and, after each one, returns the k-th largest number seen so far.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: after each new number, what's the k-th largest so far?
Why this works: keep only the k largest numbers in a min-heap; its smallest (the top) is the k-th largest.
Example: k = 3, start [4, 5, 8, 2] → heap {4, 5, 8}
add 3 → {3,4,5,8} → drop 3 → top 4add 5 → {4,5,5,8} → drop 4 → top 5add 10 → drop 5 → {5, 8, 10} top 5
✦Hints open one at a time
Keep only the k largest numbers.
In a min-heap of size k, the smallest of them — the top — is the k-th largest overall.
↗Approach
Add each number to a PriorityQueue; if it grows beyond k, poll the smallest. peek() is the answer.
</>Solution (Java)
import java.util.*;
class KthLargest {
private final int k;
private final PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap
public KthLargest(int k, int[] nums) {
this.k = k;
for (int x : nums) add(x);
}
public int add(int val) {
heap.offer(val);
if (heap.size() > k) heap.poll(); // drop the smallest
return heap.peek();
}
}!Common mistake
Using a max-heap of everything and popping k times on each call.
Complexity
- Time: O(log k) per add.
- Space: O(k).
Topic: Heaps & Priority Queue
🎬 Episodes 64–68: video coming soon