The size-K heap trick
All three problems share one move: maintain a heap holding only the K best candidates seen so far. The trick is the direction: to keep the K largest values, use a min-heap so the smallest of your keepers sits at the root, ready to be kicked out the moment something bigger arrives.
Push each element; if the heap exceeds K, pop the root. After one pass the heap holds exactly the K you want, and its root is the Kth element. K Closest Points is the same idea with distance as the key (max-heap of size K by distance).
// Kth largest → MIN-heap of size K
for x in nums:
heap.push(x)
if heap.size() > K:
heap.pop() # drop smallest
return heap.top() # Kth largest
for x in nums:
heap.push(x)
if heap.size() > K:
heap.pop() # drop smallest
return heap.top() # Kth largest
Time Complexity
O(N log K)
N pushes/pops on a heap capped at size K. Far better than sorting's O(N log N) when K is small.
Space Complexity
O(K)
The heap never grows past K elements.
Live Visualization
keep the 2 largest
Scanning input
Pushed to heap
Popped (evicted)
Heap root
Input array
Heap as a tree min-heap
Heap as an array (index 0 = root)
Result
scanning = –
heap size = 0 / K
root = –
result = –
Step 0 / 0
Scanning
–
current element
Heap size
0
capped at K
Root (evict next)
–
smallest kept
Result
–
final answer
Set K, pick a mode, and hit Play to watch the size-K heap in action.
✓ Done
Speed
Step-by-step trace
| # | Action | Element | Heap (root first) | Size | Root |
|---|
C++ — Kth Largest (LC 215)