Kth Largest Element in a Stream
Design a class to find the kth largest element in a stream using a min-heap of size k.
Kth Largest Element in a Stream
Problem: Design a class KthLargest that finds the kth largest element in a stream of numbers. It must support:
KthLargest(k, nums)— initialize with k and an initial list of numbers.add(val)— add a new number and return the current kth largest.
Example:
KthLargest(3, [4, 5, 8, 2])— 3rd largest is4add(3)→ stream[2,3,4,5,8]→ 3rd largest =4add(5)→ stream[2,3,4,5,5,8]→ 3rd largest =5
Note
The kth largest is the smallest element in the top-k set. A min-heap of exactly size k always has that answer at its root — accessible in O(1).
How to Think About It
Starting point: Store all numbers. On each add, sort the full array and return the element at position len - k. O(n log n) per add — fine for a few adds, terrible for a stream.
The realization: Every time add is called, you're re-sorting data that was already sorted. That's wasted work. What stays stable between calls?
The invariant: The k-th largest equals the minimum of the top-k set. If you maintain a min-heap that always contains exactly the k largest numbers seen so far, the root is always the answer.
The algorithm: On each add, push the new value. If the heap size exceeds k, pop the minimum (it can't be in the top-k). The root is your answer in O(1). Each add costs only O(log k), not O(n log n).
Initialization: On KthLargest(k, nums), process the initial array the same way — push each value and trim if needed. The heap is ready before the first add call.
Brute Force
View Brute Force
Optimal — Min-Heap of Size k
View Optimal Solution
| Approach | add Time | Space |
|---|---|---|
| Sort on every add | O(n log n) | O(n) |
| Min-Heap of size k | O(log k) | O(k) |