Smallest Number in Infinite Set
The key idea
Split the infinite set into two parts: a contiguous tail
[cur, cur+1, ...] that has never been touched (tracked by a single counter cur), and the handful of small numbers that were added back below cur (kept in a min-heap plus a set to reject duplicates). The smallest element is always either the heap's root or cur.Problem
You have a set which contains all positive integers [1, 2, 3, 4, 5, ...].
Implement the SmallestInfiniteSet class:
- SmallestInfiniteSet() initializes the object to contain all positive integers.
- int popSmallest() removes and returns the smallest integer currently contained in the infinite set.
- void addBack(int num) adds the positive integer num back into the infinite set, if it is not already in the set.
Since the set is conceptually infinite, you must support these operations without ever materializing every integer.
Constraints
1 <= num <= 1000- At most
1000calls will be made in total topopSmallestandaddBack.
Examples
Input: ["SmallestInfiniteSet","addBack","popSmallest","popSmallest","popSmallest","addBack","popSmallest","popSmallest","popSmallest"]
[[],[2],[],[],[],[1],[],[],[]]
Output: [null,null,1,2,3,null,1,4,5]
Complexity
Time: O(log n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Heap / Priority Queue problems
- Find K Pairs with Smallest SumsMEDIUM
- Find Median from Data StreamHARD
- IPOHARD
- K Closest Points to OriginMEDIUM
- Kth Largest Element in a StreamEASY
- Kth Largest Element in an ArrayMEDIUM
- Last Stone WeightEASY
- Maximum Subsequence ScoreMEDIUM
- Meeting Rooms IIMEDIUM
- Meeting Rooms IIIHARD
- Merge k Sorted ListsHARD
- Minimum Interval to Include Each QueryHARD