Kth Largest Element in a Stream
Easy· min-heap· top k
Problem
Design a class that is built from k and an initial list of numbers. Each call to add(val) inserts a new number and returns the kth largest value seen so far (counting duplicates).
Examples
Input: k = 3, nums = [4,5,8,2]; add(3), add(5), add(10), add(9), add(4)
Output: [4,5,5,8,8]
After add(3) the values are 2,3,4,5,8, whose third largest is 4.
Constraints
- • 1 <= k <= 10^4
- • 0 <= nums.length <= 10^4
- • At least k values exist whenever the kth largest is requested
Hints & approach
Hint 1
You never need values smaller than the current kth largest.
Hint 2
Keep only the k largest values seen so far.
Hint 3
A min-heap of size k keeps the kth largest right at the top.
Approachtry the hints first
Maintain a min-heap that holds at most k elements. Push every initial number, popping whenever the size exceeds k. For add, push the value and pop if the size is now k + 1. The heap then contains exactly the k largest values, and its minimum, at the root, is the kth largest overall.
Time O(log k) per add · Space O(k)