You have a set which contains all positive integers [1, 2, 3, 4, 5, ...].
Implement the SmallestInfiniteSet class:
SmallestInfiniteSet() Initializes the SmallestInfiniteSet object to contain all positive integers.int popSmallest() Removes and returns the smallest integer contained in the infinite set.void addBack(int num) Adds a positive integer num back into the infinite set, if it is not already in the infinite set.
Example 1:
Input
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
Output
[null, null, 1, 2, 3, null, 1, 4, 5]
Explanation
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2); // 2 is already in the set, so no change is made.
smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set.
smallestInfiniteSet.addBack(1); // 1 is added back to the set.
smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and
// is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.
Constraints:
1 <= num <= 10001000 calls will be made in total to popSmallest and addBack.Problem Overview: You design a data structure that represents an infinite set of positive integers starting from 1. The structure must support two operations: popSmallest(), which removes and returns the smallest available number, and addBack(num), which inserts a previously removed number back into the set.
Approach 1: Priority Queue + Hash Set (O(log n) per operation)
This approach explicitly tracks numbers that were removed and later reinserted. Maintain a min-heap storing values returned through addBack and a hash set to avoid duplicates. Also keep a pointer current representing the smallest number that has never been popped from the infinite sequence. When popSmallest() runs, compare the heap's smallest element with current. If the heap contains a smaller value, remove it from the heap and set; otherwise return current and increment the pointer. When addBack(num) is called, insert num into the heap only if it is smaller than current and not already tracked in the set. Heap operations cost O(log n) time and the set ensures constant-time membership checks. Space complexity is O(n) for stored reinserted values. This design is a classic combination of heap (priority queue) ordering with fast lookups using a hash table.
Approach 2: Indexed Array with Flags (O(1) amortized)
Because the number of operations is bounded, you can simulate the infinite set using a boolean array that tracks whether a number has been removed or added back. Maintain a pointer pointing to the current smallest candidate. When popSmallest() runs, move the pointer forward until you find an index marked available, mark it removed, and return it. For addBack(num), simply flip the flag back to available if the number was previously removed. Each element is scanned at most once during pointer advancement, giving O(1) amortized time for popSmallest() and O(1) for addBack(). Space complexity is O(n) for the flag array. This approach works well when operation limits are small and avoids the overhead of heap operations or maintaining an ordered set.
Recommended for interviews: The priority queue + set approach is the one most interviewers expect. It models the infinite sequence cleanly using a pointer and handles reinserted values efficiently with heap ordering. Implementing it shows you understand heap behavior, duplicate prevention, and state management in a design-style problem. The indexed array method is simpler but depends on constraints; it demonstrates optimization awareness once the baseline design is clear.
In this approach, we keep track of removed numbers using a priority queue (min heap) and a set to allow efficient look-up, addition, and removal operations. The priority queue keeps the numbers in sorted order, allowing us to quickly access and remove the smallest number. The set helps us to efficiently check whether a number needs to be added back.
The implementation uses a min-heap (priority queue) to keep numbers in sorted order. We have a boolean array, present[], to keep track of numbers currently in the heap.
Time Complexity: O(log n) for both pop and add operations, where n is the size of the heap.
Space Complexity: O(n), where n is the size of the heap.
In this methodology, we use an integer array to monitor the appearance of each number and a boolean flag array to verify if a number is within the set. This leverages more direct array manipulations without complex data structures.
This approach leverages direct manipulations with an array marked as a flag to represent the presence of a number.
Time Complexity: O(1) for addBack(), O(1) for popSmallest() in average case due to direct access using index.
Space Complexity: O(n), trials with fixed space that holds states up to MAX integers.
We note that the range of elements in the set given by the problem is [1, 1000], and the operations we need to support are:
popSmallest: Pop the smallest element from the setaddBack: Add an element back to the setTherefore, we can use an ordered set to simulate this. Let's denote the ordered set as s, and the elements in the set as s_1, s_2, cdots, s_n, where n is the number of elements in the ordered set. In this problem, n \le 1000.
During initialization, we add all elements in [1, 1000] to the ordered set. The time complexity is O(n times log n).
In the popSmallest operation, we just need to pop the first element from the ordered set. The time complexity for a single operation is O(log n).
In the addBack operation, we just need to add the element back to the ordered set. The time complexity for a single operation is O(log n).
The space complexity is O(n).
| Approach | Complexity |
|---|---|
| Approach using Priority Queue and Set | Time Complexity: O(log n) for both pop and add operations, where n is the size of the heap. Space Complexity: O(n), where n is the size of the heap. |
| Approach using Indexed Array and Flags | Time Complexity: O(1) for addBack(), O(1) for popSmallest() in average case due to direct access using index. Space Complexity: O(n), trials with fixed space that holds states up to MAX integers. |
| Ordered Set + Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Priority Queue + Hash Set | O(log n) per operation | O(n) | General solution for design interviews where numbers can be reinserted dynamically |
| Indexed Array with Flags | O(1) amortized | O(n) | When operation limits are small and a bounded simulation of the infinite set is acceptable |
Smallest Number in Infinite Set | 3 Approaches | (MICROSOFT) | Leetcode 2336 | Live Code 🧑🏻💻 • codestorywithMIK • 8,165 views views
Watch 9 more video solutions →Practice Smallest Number in Infinite Set with our built-in code editor and test cases.
Practice on FleetCode