Smallest Number in Infinite Set
Medium · Heap & Counting · Hash Table · Design · Heap (Priority Queue) · Ordered Set
Problem
Design a set that starts out containing every positive integer 1, 2, 3, ....
Implement SmallestInfiniteSet:
- SmallestInfiniteSet() creates the set with all positive integers.
- popSmallest() removes the smallest number in the set and returns it.
- addBack(num) puts num back into the set if it is not already there; otherwise it does nothing.
The input is the list of operations and the list of their arguments, and the output lists what each call returns (null for the constructor and for addBack).
Examples
Input: ops = ["SmallestInfiniteSet","popSmallest","popSmallest","addBack","popSmallest","popSmallest","addBack"], args = [[],[],[],[1],[],[],[5]] Output: [None, 1, 2, None, 1, 3, None]
1 and 2 are removed; 1 is added back and popped again; then 3 is next. Adding 5 back does nothing, since 5 is still in the set.
Input: ops = ["SmallestInfiniteSet","addBack","popSmallest"], args = [[],[4],[]] Output: [None, None, 1]
4 was never removed, so the smallest is still 1.
Input: ops = ["SmallestInfiniteSet","popSmallest","popSmallest","popSmallest","addBack","addBack","popSmallest","popSmallest","popSmallest"], args = [[],[],[],[],[3],[1],[],[],[]] Output: [None, 1, 2, 3, None, None, 1, 3, 4]
3 and 1 are added back; pops return 1, then 3, then 4 from the untouched tail.
Constraints
- 1 <= num <= 1000
- At most 1000 calls are made to popSmallest and addBack combined
Approaches
- Remember removed numbers, scan up from 1 — time O(M) per pop, M = largest removed, space O(M)
Follow-up
What if numbers could be as large as 10^9 and calls ran to 10^5? The pointer-plus-heap design does not care: its cost depends only on how many numbers were added back. The scanning baseline, though, slows down with every number removed.
Related problems
Start free on Cariara · Coding problems · System design studio
