Kth Largest Element in a Stream
Design a class that returns the kth largest value after each new number arrives, by keeping a min-heap of the k largest values between calls.
Problem Understanding
Kth Largest Element in a Stream (LeetCode 703): design a class KthLargest. The constructor KthLargest(k, nums) receives k and the starting numbers. Each call to add(val) appends val to the stream and returns the kth largest value in the stream so far. Duplicates count separately.
Example: KthLargest(3, [4, 5, 8, 2]), then add(3), add(5), add(10), add(9), add(4) return 4, 5, 5, 8, 8.
The Intuition: Only k Values Ever Matter
Once a number is smaller than k others, it can never be the kth largest again: the stream only grows, so more numbers can only push it further down. That means you only ever need to remember the k largest values.
- Keep them in a min-heap. The smallest of the k largest is the kth largest, and a min-heap keeps it at the root.
- On add(val), push val. If the heap now holds k + 1 values, pop the minimum. It just lost its place for good.
- Return the root.
The constructor is just add() called on every starting number. The one-shot version of the same idea is Kth Largest Element in an Array, and Find Median from Data Stream keeps two heaps between calls in the same way.
Interactive Walkthrough
k = 3 · ROOT = 3RD LARGEST
CONSTRUCTOR
KthLargest(3, nums)
add(val) · returns
empty heap
heap array · at most k = 3
Size
0/3
Root
:
Returned
:
KthLargest(3, nums): store k = 3 and start an empty min-heap
Next
Constructor: add nums[0] = 4 (its return value is ignored)
nums
add
k
Legend & Complexity
The number being added, or the value moving in the heap
The parent or child it was swapped with
The minimum popped: too small to be in the top k
The root add() returns: the kth largest so far
add()
O(log k)
Constructor
O(n log k)
Space
O(k)
The constructor's numbers come first, then each add() call with the value it returned underneath. Watch the heap: it never holds more than k values once a call finishes. Try Small adds: every small value is pushed and popped straight back out, and the answer does not move.
Dry Run Table
Input: KthLargest(3, [4, 5, 8, 2]), then add(3), add(5), add(10), add(9), add(4). The heap is shown as its array, root first.
| Call | Popped | Heap after | Returns |
|---|---|---|---|
| constructor adds 4, 5, 8 | none | [4, 5, 8] | (ignored) |
| constructor adds 2 | 2 | [4, 5, 8] | (ignored) |
| add(3) | 3 | [4, 5, 8] | 4 |
| add(5) | 4 | [5, 5, 8] | 5 |
| add(10) | 5 | [5, 10, 8] | 5 |
| add(9) | 5 | [8, 9, 10] | 8 |
| add(4) | 4 | [8, 9, 10] | 8 |
Returns: 4, 5, 5, 8, 8.
The Solution Template
A min-heap stored in the object. JavaScript, TypeScript and C have no built-in heap, so each snippet includes a small one.
Kth Largest Element in a Stream Code
1class Heap {2 constructor(before) {3 this.items = [];4 this.before = before;5 }67 size() {8 return this.items.length;9 }1011 peek() {12 return this.items[0];13 }1415 push(item) {16 const a = this.items;17 a.push(item);18 let i = a.length - 1;19 while (i > 0 && this.before(a[i], a[(i - 1) >> 1])) {20 const parent = (i - 1) >> 1;21 [a[i], a[parent]] = [a[parent], a[i]];22 i = parent;23 }24 }2526 pop() {27 const a = this.items;28 const top = a[0];29 const last = a.pop();30 if (a.length > 0) {31 a[0] = last;32 let i = 0;33 while (true) {34 const left = 2 * i + 1, right = 2 * i + 2;35 let first = i;36 if (left < a.length && this.before(a[left], a[first])) first = left;37 if (right < a.length && this.before(a[right], a[first])) first = right;38 if (first === i) break;39 [a[i], a[first]] = [a[first], a[i]];40 i = first;41 }42 }43 return top;44 }45}4647class KthLargest {48 constructor(k, nums) {49 this.k = k;50 this.heap = new Heap((a, b) => a < b);51 for (const num of nums) {52 this.add(num);53 }54 }5556 add(val) {57 this.heap.push(val);58 if (this.heap.size() > this.k) {59 this.heap.pop();60 }61 return this.heap.peek();62 }63}
Edge Cases & Common Mistakes
- nums shorter than k: allowed (k - 1 numbers). The first add() fills the heap; do not read the root before it does.
- k = 1: the heap holds one value, the maximum so far.
- Duplicates: equal values each take a place in the heap; this is not the kth distinct value.
- Negative numbers: the heap compares values directly, so negatives need no special handling.
- Rebuilding on every call: sorting or heapifying the whole stream in add() is O(n log n) per call. Keep the heap in the object.
- Using a max-heap: its root is the largest value, not the kth largest.
Summary
Keep a min-heap of the k largest values inside the object. add(val) pushes, pops the minimum if the heap grows past k, and returns the root. O(log k) per add(), O(n log k) for the constructor, O(k) space.
More practice: DSA interview questions with answers · patterns cheat sheet