DSA Tracker

Visualize

Kth Largest Element in a Stream

A size-k min-heap: the root is always the answer

time O((n + m) log k)space O(k)

The stream can grow forever, but only rank k ever matters — anything smaller than the kth largest can never become it and never displace it either. So keep just the k largest values seen so far in a min-heap: its root, the smallest of that top-k group, is by definition the kth largest overall. Every add is push, evict the new smallest if the heap overflows past k, then read the root.

Details

Animated on: Design a class that finds the kth largest element in a growing stream. Constructed with k=3 and nums=[4,5,8,2], then add(3), add(5), add(10), add(9), add(4) must return [4, 5, 5, 8, 8].

Problem:Kth Largest Element in a StreamEasy

Pattern:Heap and Top K

A size-k min-heap: the root is always the answer

step 1 / 12

4

Constructor pushes 4 from the initial array. Heap now holds [4] — still under capacity k=3, so nothing is evicted yet.

Pseudocode
1FUNCTION KthLargest(k, nums):
2  heap <- EMPTY MIN-HEAP
3  FOR num IN nums:
4    PUSH num INTO heap
5    IF SIZE(heap) > k:
6      POP-MIN(heap)
7FUNCTION add(val):
8  PUSH val INTO heap
9  IF SIZE(heap) > k:
10    POP-MIN(heap)
11  RETURN heap[0]

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. Constructor pushes 4 from the initial array. Heap now holds [4] — still under capacity k=3, so nothing is evicted yet.
  2. Constructor pushes 5 from the initial array. Heap now holds [4, 5] — still under capacity k=3, so nothing is evicted yet.
  3. Constructor pushes 8 from the initial array. Heap now holds [4, 5, 8] — still under capacity k=3, so nothing is evicted yet.
  4. Pushing 2 grows the heap to size 4, past capacity k=3. It bubbled up to the root because 2 is the smallest value seen so far — a min-heap always keeps its smallest at the top, which is exactly the item about to get evicted.
  5. size(heap) > k, so pop-min fires: the root (2) is discarded and the heap shrinks back to [4, 5, 8]. Construction is done — these are the 3 largest values seen so far, smallest on top.
  6. add(3) pushes onto the heap. It sifted up to become the new root, so 3 is currently the smallest of the 4 values held — heap is one over capacity again.
  7. Evicting the root (3) brings the heap back to size 3: [4, 5, 8]. Its new root, 4, is the smallest of the top 3 — by definition the 3rd largest of the whole stream. add(3) returns 4.
  8. add(5): push, then pop-min evicts 4 since the heap is over capacity again. Heap settles at [5, 5, 8] and returns its root, 5 — the same push-then-evict shape every call follows.
  9. add(10): push, then pop-min evicts 5 since the heap is over capacity again. Heap settles at [5, 10, 8] and returns its root, 5 — the same push-then-evict shape every call follows.
  10. add(9): push, then pop-min evicts 5 since the heap is over capacity again. Heap settles at [8, 9, 10] and returns its root, 8 — the same push-then-evict shape every call follows.
  11. add(4): push, then pop-min evicts 4 since the heap is over capacity again. Heap settles at [8, 9, 10] and returns its root, 8 — the same push-then-evict shape every call follows.
  12. Full call sequence returns [4, 5, 5, 8, 8], matching the problem's own worked example. Each push/pop only touches a heap of size k, so every add() costs O(log k) instead of resorting the whole stream.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Kth Largest Element in a Stream in the editorAll Heap problemsBack to roadmap