664. Smallest Number in Infinite Set
Picture a container that starts out holding every positive integer: 1, 2, 3, 4, … all the way up. Design a class SmallestInfiniteSet with two operations:
popSmallest()— remove the smallest number currently in the container and return it.addBack(num)— putnumback into the container. Ifnumis already in the container, this does nothing (the container never holds duplicates).
Your program receives a sequence of operations and must report the value returned by every popSmallest call, in order.
The set is infinite, so you obviously cannot store it — the trick is to represent only how it differs from 1, 2, 3, ….
Example 1:
Input: addBack(2), popSmallest() ×3, addBack(1), popSmallest() ×3
Output: [1, 2, 3, 1, 4, 5]
Explanation: The first addBack(2) changes nothing — 2 is still in the set. Three pops return 1, 2, 3. addBack(1) re-inserts 1, so the next pop returns 1 again, and the following pops return 4 and 5.
Example 2:
Input: popSmallest(), popSmallest(), addBack(1), popSmallest()
Output: [1, 2, 1]
Explanation: Pops return 1 then 2. After addBack(1) the smallest element is 1 again, so the last pop returns 1.
Constraints:
- 1 ≤ num ≤ 1000 for every addBack(num)
- 1 ≤ q ≤ 1000 total operations
- At least one operation is a pop.
Hints:
The set only ever differs from {1, 2, 3, …} in finitely many places: some prefix numbers have been popped, and some of those may have been added back. Store the difference, not the set.
Keep a counter `next` = the smallest number that has never been popped. Every number >= next is definitely in the set; the only other members are popped-then-re-added numbers below next.
Store those re-added numbers in a min-heap (plus a hash set to block duplicates). popSmallest: if the heap is non-empty its top beats `next`; otherwise return next and bump it. addBack(num): only matters when num < next and not already in the heap.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: addBack(2), pop, pop, pop, addBack(1), pop, pop, pop
Expected output: [1, 2, 3, 1, 4, 5]