Kth Largest Element In a Stream
The briefingthe full drill, in my own words
The drill: A running stream of numbers where each new value must instantly reveal the kth largest seen so far — the structure has to answer that question the moment a number lands, not by re-sorting everything.
Numbers arrive one at a time into a live stream, and after every new number lands, the structure needs to instantly report the kth largest value seen across the whole stream so far.
The stream can start already holding some numbers before the first live add happens, and k stays fixed for the life of the structure — only the pool of numbers keeps growing from there.
Each add operation both records the new number and returns the current kth largest in one step, so the answer must be ready immediately, not computed by rescanning history.
- k stays fixed once the structure is created
- the stream is guaranteed to hold at least k numbers after each add
- values can repeat and can be negative, zero, or positive
- each add must answer with the current kth largest immediately
The hintstake only what you need
HINT 1 THE NUDGE
Re-sorting after every new number answers the question correctly but pays for the whole stream again and again. What's the smallest slice of the stream you actually need to remember to answer 'kth largest' instantly?
HINT 2 THE STRUCTURE
You never need the whole history — only the k largest values seen so far actually matter, and among those k, the smallest one IS the answer.
HINT 3 ONE STEP FROM THE ANSWER
Keep a min-heap capped at size k: push the new value, and if the heap grows past k, pop its smallest. The heap's top is always the kth largest.
Coach's boardthe pattern, step by step
Seed [4, 5, 8, 2] with k=3 — heapify, then pop down to the 3 largest: 4, 5, 8.
The splitstwo paces, two languages
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.heap = list(nums)
heapq.heapify(self.heap)
while len(self.heap) > k:
heapq.heappop(self.heap)
def add(self, val: int) -> int:
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap)
return self.heap[0]class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.nums = list(nums)
def add(self, val: int) -> int:
self.nums.append(val)
self.nums.sort(reverse=True) # re-sort the whole stream every time
return self.nums[self.k - 1]class KthLargest {
private final int k;
private final PriorityQueue<Integer> heap = new PriorityQueue<>();
public KthLargest(int k, int[] nums) {
this.k = k;
for (int v : nums) {
heap.offer(v);
if (heap.size() > k) {
heap.poll();
}
}
}
public int add(int val) {
heap.offer(val);
if (heap.size() > k) {
heap.poll();
}
return heap.peek();
}
}class KthLargest {
private final int k;
private final List<Integer> nums = new ArrayList<>();
public KthLargest(int k, int[] nums) {
this.k = k;
for (int v : nums) {
this.nums.add(v);
}
}
public int add(int val) {
nums.add(val);
nums.sort(Collections.reverseOrder());
return nums.get(k - 1);
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED