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).
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) |