Track the kth largest number as new ones stream in. Keep only the top k in a min-heap, and its smallest member is always the answer.
▼The problem
LeetCode 703 (Easy). Design a class KthLargest(k, nums) with a method add(val) that adds val to the stream and returns the k-th largest number seen so far (the k-th in sorted order, duplicates counted).
Example (LeetCode's): k = 3, nums = [4, 5, 8, 2]; add(3) → 4, add(5) → 5, add(10) → 5, add(9) → 8, add(4) → 8.
The solution
import heapq
class KthLargest:
def __init__(self, k, nums):
self.k = k
self.heap = []
for x in nums:
self.add(x)
def add(self, val):
if len(self.heap) < self.k:
heapq.heappush(self.heap, val)
else:
heapq.heappushpop(self.heap, val)
return self.heap[0]Transcript
K-th Largest Element in a Stream. Numbers arrive one at a time. Design a class that takes k and some starting numbers, and after every add, returns the k-th largest so far.
Say k is three, and we start with four, five, eight and two. Add three, and the third largest is four. Add five: five. Then ten gives five, nine gives eight, and four still gives eight.
The naive way keeps every number sorted and counts down k from the top. But each add shifts a growing list: order n.
Better: only the top k matter. Keep them in a min-heap of size k, like a club with three seats. The smallest sits on top, by the door, and that's the answer. A bigger newcomer bounces it and takes a seat. Anyone else is turned away.
In code: while there's room, push. Once full, heap push pop swaps the newcomer in only if it beats the top. Return the top.
On the example: four, five and eight take the seats, and two is turned away. Three is turned away, so four. Five bounces four: five. Ten bounces a five: still five. Nine bounces the other five: eight. And four is turned away: eight.
Each add costs order log k time, and the heap holds just k numbers: order k space.
Keep the top k, guard the smallest, and read it off the top. That's K-th Largest Element in a Stream.