Pattern visualizer

Kth Largest Element in a Stream

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. 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]..

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

time O((n + m) log k)space O(k)step 1 / 12

line 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

Where to practice Heap

Practice Heap problems All Heap problems Back to roadmap