04
Streaming / dynamic (Heap — Top K Sub-pattern)
A class answers queries while items arrive (or are taken and returned). Keep the heap alive between calls so each call is O(log K) or O(log N).
Signals in the problem statement
- ›
"design a class that returns the kth largest after each add"
- ›
"pop the smallest available number; numbers can be added back"
- ›
"reserve the lowest free seat; seats can be unreserved"
What makes it different
Kth Largest in a Stream keeps a size-K min-heap. Smallest Number in Infinite Set and Seat Reservation Manager are "smallest free ID" problems. A counter next covers every ID never handed out, and a min-heap holds only the IDs that were given back. That avoids filling a heap with every ID up front. In the infinite set, a number can be added back twice, so a hash set stops duplicates.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Kth Largest Element in a StreamWalkthroughEasyBasic Anchor·LeetCode #703
- 2Smallest Number in Infinite SetWalkthroughMediumBasic Reinforcement·LeetCode #2336
- 3Seat Reservation ManagerWalkthroughMediumSlight Variation·LeetCode #1845
Template
stream-template.cpp
// Kth largest in a stream: the size-k min-heap lives inside the class.
class KthLargest {
int k;
priority_queue<int, vector<int>, greater<int>> pq; // the k largest so far
public:
KthLargest(int k, vector<int>& nums) : k(k) {
for (int x : nums) add(x);
}
int add(int val) {
pq.push(val);
if ((int)pq.size() > k) pq.pop();
return pq.top(); // O(log k) per call
}
};Remember this · Heap — Top K
Trigger
"K largest / smallest / most frequent / closest", kth element, streaming top-K.
Think
Do I really need everything sorted, or only the best K?
Key question
Min-heap or max-heap of size K — which one lets me kick out the worst candidate?