LeetCode 703 · Easy · Heap / Priority Queue

Kth Largest Element in a Stream

Build a class from k and a starting list nums; every call to add(val) inserts a value and returns the k-th largest value seen so far.

O(log k)per add
O(k)space
size kmin-heap

k: 1–9, at most nums.length + 1 · nums: 0–8 values · adds: 1–8 values · integers −99 to 99

Stream add(val) calls · each one's return value below it

minHeap tree · every parent ≤ its children

Popped for good

minHeap list children of i sit at 2i + 1 and 2i + 2

class KthLargest { private final PriorityQueue<Integer> minHeap; private final int k; public KthLargest(int k, int[] nums) { this.k = k; List<Integer> list = new ArrayList<>(); for (int n : nums) { list.add(n); } minHeap = new PriorityQueue<>(list); // heapify while (minHeap.size() > k) { minHeap.poll(); } } public int add(int val) { minHeap.offer(val); if (minHeap.size() > k) { minHeap.poll(); } return minHeap.peek(); }}
k
—
val
—
minHeap.size()
0
minHeap
[]
returned
[]

Why it works

  1. Brute force keeps everything sorted: each add inserts into a sorted list (O(n) shifting) or re-sorts (O(n log n)), and memory grows with the whole stream.
  2. Only the top k matter. Keep exactly the k largest values in a min-heap. The smallest of them sits at the root, and that is the k-th largest overall. Anything below the root can never be the answer again, so pop it.
  3. Push, then pop if too big: the heap briefly holds k + 1 values, and poll() throws out the smallest. Each add is O(log k); the constructor is an O(n) heapify (the PriorityQueue(Collection) constructor) plus (n − k) polls. Space O(k).
  4. How the heap moves: push appends a leaf and sifts it up past larger parents; pop moves the last leaf to the root and sifts it down past its smaller child. At most log₂(size) swaps each.
  5. Pitfalls: the constructor needs while, not if, because nums can be much longer than k. A max-heap is the wrong tool: its root is the largest, not the k-th largest.
  6. Follow-up: 215 Kth Largest Element in an Array uses the same size-k heap, or quickselect for O(n) average. 347 Top K Frequent Elements is the same pattern keyed by count.