DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Kth Largest Element in a Stream

easyHeaps and top-K

Problem statement

Build a class KthLargest that tracks the k-th largest value in a growing stream of integers.

  • The constructor receives k and an initial list nums (which may have fewer than k values).
  • add(val) adds val to the stream and returns the k-th largest value seen so far, counting duplicates separately.

You can assume that whenever add is called, the stream will contain at least k values after adding.

Examples

Example 1

Input: KthLargest(3, [5, 1, 8]) add(4), add(10), add(2), add(9)

Output: 4, 5, 5, 8

Explanation: After add(4) the values sorted high to low are 8, 5, 4, 1, so the third largest is 4. After add(9) the top three are 10, 9, 8.

Example 2

Input: KthLargest(1, []) add(-3), add(-7), add(0)

Output: -3, -3, 0

Explanation: With k = 1 the answer is just the maximum so far.

Hints

Approach

Keep only the k largest values, in a min-heap.

  1. Build the heap by feeding the initial nums through the same add logic.
  2. On add(val): push val. If the heap now holds more than k values, pop the smallest.
  3. The heap root is the smallest of the k largest values, which is exactly the k-th largest. Return it.

A value that gets popped is smaller than k others already seen, so it can never become the answer again, no matter what arrives later. That is why throwing it away is safe.

ComplexityTime O(log k) per add, O(n log k) to buildSpace O(k)
Python
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

Follow-up questions

  • Support removing a value from the stream as well.
  • Track the median of the stream instead (two heaps).

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.

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.

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.