Kth Largest Element in a Stream
Problem statement
Build a class KthLargest that tracks the k-th largest value in a stream of integers that keeps growing.
- The constructor receives
kand a starting listnums. The list may hold fewer thankvalues. add(val)addsvalto the stream and returns thek-th largest value seen so far. Equal values count separately.
You can assume that after every add call the stream holds at least k values.
Examples
Example 1
Input: KthLargest(3, [4, 5, 8, 2])
add(3), add(5), add(10), add(9), add(4)
Output: [null, 4, 5, 5, 8, 8]
Explanation: The constructor returns nothing (null). After add(3) the values from high to low are 8, 5, 4, 3, 2, so the third largest is 4. After add(5) they are 8, 5, 5, 4, ..., so it is 5. After add(10) the top three are 10, 8, 5, so it is 5. After add(9) the top three are 10, 9, 8, so it is 8. Adding 4 does not enter the top three, so the answer stays 8.
Hints
add is correct. Ask yourself how many of the values you really need to keep.Approach
Optimal: Min-heap of size k
Intuition
The sorted list needed O(k) shifting just to insert one value. A min-heap keeps its smallest value at the root and can add or remove a value in O(log k) steps, with no shifting. Keep the k largest values in a min-heap. The root is then the smallest of the top k, which is the k-th largest of the whole stream. When a new value arrives, push it. If the heap now holds more than k values, pop the root: that value is smaller than k others already seen, so it can never be the answer again.
Steps
- Create an empty min-heap and feed the starting values through the
addlogic. - On
add(val), pushvalonto the heap. - If the heap holds more than
kvalues, pop the smallest. - Return the root of the heap (the smallest value in it).
Dry run
k = 3, start [4, 5, 8, 2]: the heap holds {4, 5, 8} after the constructor (2 was pushed and popped).
| call | heap after push | after pop if over k | root (answer) |
|---|---|---|---|
| add(3) | {3, 4, 5, 8} | pop 3 → {4, 5, 8} | 4 |
| add(5) | {4, 5, 5, 8} | pop 4 → {5, 5, 8} | 5 |
| add(10) | {5, 5, 8, 10} | pop 5 → {5, 8, 10} | 5 |
| add(9) | {5, 8, 9, 10} | pop 5 → {8, 9, 10} | 8 |
| add(4) | {4, 8, 9, 10} | pop 4 → {8, 9, 10} | 8 |
Edge cases: with k = 1 the heap holds one value, the maximum so far. A new value smaller than the root is pushed and popped immediately, which is correct.
Complexity
Time O(log k) - per `add`, O(n log k) to build - A push into a heap of at most k + 1 values and a pop both take O(log k). The root is read in O(1). Feeding the n starting values through `add` costs n times log k.
Space O(k) - The heap never holds more than k values after each `add`. Everything smaller is discarded. Memory stays fixed however long the stream runs.
import heapq
class KthLargest:
def __init__(self, k: int, nums: list[int]):
self.k = k
self.heap = [] # min-heap holding the k largest values seen
for x in nums:
self.add(x)
def add(self, val: int) -> int:
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap) # drop the smallest; it can never be the answer again
return self.heap[0] # smallest of the top k = kth largest
if __name__ == "__main__":
kl = KthLargest(3, [4, 5, 8, 2])
print("[null, " + ", ".join(str(kl.add(v)) for v in [3, 5, 10, 9, 4]) + "]")RecapThe whole problem in a few lines, for the night before
- Spot it: after every new number, report the kth largest so far
- Idea: keep a min-heap of size k; the top of the heap is always the kth largest; push each new value and pop when the size goes above k
- Cost: O(log k) per add, O(k) space
- Trap: use a min-heap (not a max-heap), so the smallest of the top k sits at the root
Interview follow-ups
Support removing a value from the stream as well.
The size-k min-heap cannot do this. It threw away every value outside the top k, so when a top value is removed, the value that should take its place is already gone. Keeping a bigger heap with lazy deletion does not fix it either, because you cannot know in advance how many values might be removed. The reliable answer is to keep every value in a balanced search tree where each node also stores the size of its subtree (an order-statistic tree). Then add, remove and "find the k-th largest" each cost O(log n), at the price of O(n) memory. If removals are rare and n is small, a sorted list with binary search is simpler, at O(n) per update.
What if
kcan change between calls?Lowering k is easy: pop from the min-heap until it holds the new k values. Raising k is the hard case, because the values you threw away earlier may now be needed. If you know the largest k you will ever see, keep a structure of that size and read the k-th largest from it. If not, you must keep every value, for example in a balanced tree with order statistics, and each query then costs O(log n) with O(n) memory.
The stream is split across many servers. How do you find the overall k-th largest?
Let each server keep its own min-heap of its k largest values, as in the optimal approach. To answer a query, collect all those heaps on one machine, put their values together, and take the k-th largest of the combined values. This is correct because the overall top k values must each be in the top k of the server that saw them. With s servers the merge handles s times k values, so a query costs about O(s · k log k), and each server still uses only O(k) memory.
Frequently asked questions
Because the question is always "what is the smallest of my top k?" and "should this new value replace the weakest of them?". A min-heap answers both at its root. A max-heap would put the largest value on top, which is not the one you need, and finding the smallest of the top k would take a full scan.
The heap simply stays smaller than k until enough values arrive. The problem guarantees that by the time add returns, there are at least k values, so the root is always a valid answer. Pushing the starting values through add handles this without a special case.
Yes. If the stream is 5, 5, 5 and k = 2, the second largest is 5. The heap stores each copy, so equal values take up separate slots, which matches the rule in the statement.
Tracking the top k of a stream in bounded memory is how you keep "the slowest 100 requests" or "the largest 10 log files" while data keeps arriving, without storing everything. It is also the building block behind approximate percentile tracking.
