Design a class that tracks the k-th largest element in a stream of integers. It is initialized with k and an initial array nums; each add(val) inserts val and returns the k-th largest element seen so far.
To exercise it here, implement kthLargestStream(k, nums, adds): construct the tracker with k and nums, then call add for each value in adds, returning the list of results. If fewer than k elements exist at some step, that result is -1.
Input: k = 3, nums = [4, 5, 8, 2], adds = [3, 5, 10, 9] Output: [4, 5, 8, 8] After each add, the 3rd largest so far is 4, 5, 8, 8.
Input: k = 1, nums = [], adds = [1, 2, 3] Output: [1, 2, 3] The 1st largest is just the running maximum.
- 1 <= k <= 10^4 - 0 <= nums.length <= 10^4 - 1 <= adds.length <= 10^4 - -10^4 <= nums[i], adds[i] <= 10^4
The naive tracker re-sorts everything on every add — O(n log n) per call. The efficient one keeps a min-heap of size k holding the k largest elements seen so far. Its root is the k-th largest, and each add is just O(log k).
Why a min-heap for the largest? It's the counterintuitive key: to guard the top k, you watch their weakest member. Push the new value; if the heap now holds more than k, pop the smallest. Whatever survives is the current top-k, and the root — the smallest of those — is exactly the k-th largest. A value smaller than the root never displaces anything; a larger one evicts the old weakest. You never store more than k elements, no matter how long the stream.
“Does add return a value?”
Yes — the k-th largest after inserting.
“What if there are fewer than k elements?”
Return -1 for that step (the k-th largest isn't defined yet).
I keep a size-k min-heap of the largest values; its root is the k-th largest.
Each add pushes the value and pops the smallest if the heap exceeds k — O(log k) per add, O(k) memory.
Worked example — k = 3, nums = [4, 5, 8, 2], then add 3, add 5, add 10, add 9
seed top-3 of [4,5,8,2] -> heap {4,5,8}, root 4
add 3 -> 3 < 4, evicted -> root 4
add 5 -> {5,5,8}, root 5
add 10 -> {5,8,10}, root 8
add 9 -> {8,9,10}, root 8
results = [4, 5, 8, 8]
Everything below the k-th largest is irrelevant to the answer.
The smallest of the k largest is the k-th largest, available in O(1).
Bounded work and space regardless of stream length.
| Re-sort per add | Size-k min-heap | |
|---|---|---|
| Idea | Sort all elements each add, take index k-1 | Keep the k largest; return the root |
| Per add | O(n log n) | O(log k) |
| Memory | O(n) | O(k) |
The heap makes each update cheap and bounds memory — essential for a real stream. Full code is in the Approaches selector below.
Key takeaway
Keep a size-k min-heap of the largest elements; the root is the k-th largest. Each add pushes and trims to k in O(log k), using O(k) memory.
add(v):
push v
if size > k: pop smallest
return root (or -1 if size < k)