Smallest Number in Infinite Set

Med

#2128Time: `popSmallest()`: O(log K), where K is the number of elements in the heap. `addBack()`: O(log K). The `contains` check on the HashSet is O(1) on average, and adding to the heap is O(log K).Space: O(K), where K is the maximum number of items that are added back. This space is used by the Min-Heap and the HashSet.

Patterns

Design

Data structures

Hash Table Heap (Priority Queue)Ordered Set

Prompt

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 <= 1000
At most 1000 calls will be made in total to popSmallest and addBack.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach models the problem by managing two groups of numbers: a contiguous block of integers starting from a point that have never been touched, and a separate collection of smaller integers that were popped and then added back. We use an integer variable, currentInteger, to track the start of the infinite sequence (initially 1). A Min-Heap is used to store the numbers added back, allowing efficient retrieval of the smallest among them. When popSmallest is called, we return the minimum of currentInteger and the smallest element in the heap. To efficiently prevent adding duplicate numbers back into the heap, an auxiliary HashSet is used.

Algorithm

Initialize an integer currentInteger to 1 to track the smallest integer in the conceptual infinite sequence.
Use a Min-Heap (like PriorityQueue in Java) to store any numbers that are added back after being popped.
To handle duplicates efficiently, use a HashSet to keep track of the numbers currently present in the Min-Heap.
For popSmallest():
- Compare the smallest element in the heap (minHeap.peek()) with currentInteger.
- If the heap is not empty and its top element is smaller than currentInteger, it is the smallest overall. Pop it from the heap and remove it from the HashSet.
- Otherwise, currentInteger is the smallest. Return it and increment it for the next call.
For addBack(num):
- A number can only be added back if it was previously popped. This means num must be smaller than currentInteger.
- Also, it must not already be in the heap (check using the HashSet).
- If both conditions are met, add num to both the heap and the HashSet.

Walkthrough

This implementation uses a counter currentInteger for the main sequence of numbers, a PriorityQueue as a min-heap for numbers added back, and a HashSet for quick lookups to avoid duplicates in the heap.

1import java.util.PriorityQueue;2import java.util.HashSet;3 4class SmallestInfiniteSet {5    private int currentInteger;6    private PriorityQueue<Integer> minHeap;7    private HashSet<Integer> isAddedBack;8 9    public SmallestInfiniteSet() {10        currentInteger = 1;11        minHeap = new PriorityQueue<>();12        isAddedBack = new HashSet<>();13    }14    15    public int popSmallest() {16        int result;17        // If the heap has a smaller number than the next in the sequence, pop from the heap.18        if (!minHeap.isEmpty() && minHeap.peek() < currentInteger) {19            result = minHeap.poll();20            isAddedBack.remove(result);21        } else {22            // Otherwise, take the next integer from the main sequence.23            result = currentInteger;24            currentInteger++;25        }26        return result;27    }28    29    public void addBack(int num) {30        // Only add back if the number is smaller than our current sequence pointer31        // and is not already in the heap.32        if (num < currentInteger && !isAddedBack.contains(num)) {33            minHeap.add(num);34            isAddedBack.add(num);35        }36    }37}

Complexity

Time

`popSmallest()`: O(log K), where K is the number of elements in the heap. `addBack()`: O(log K). The `contains` check on the HashSet is O(1) on average, and adding to the heap is O(log K).

Space

O(K), where K is the maximum number of items that are added back. This space is used by the Min-Heap and the HashSet.

Trade-offs

Pros

It's a general solution that works even if the numbers or the number of calls were much larger, as its space complexity depends on the number of addBack calls, not the magnitude of the numbers.
It correctly models the "infinite" nature of the set without relying on a fixed-size array.
The logarithmic time complexity is very efficient for general cases.

Cons

Slightly more complex to implement than a simple array-based approach.
For the given constraints, it might be slightly slower than an optimized array-based solution due to the overhead of heap operations (O(log K) vs O(1) amortized).

Given the problem's constraints (num <= 1000, at most 1000 calls), the numbers involved will stay within a limited range. This allows for a highly optimized approach using a simple boolean array to track the presence of each number. We can pre-allocate an array (e.g., of size 2002) where isPresent[i] tells us if number i is in the set. A pointer, smallestPtr, is maintained to keep track of the smallest known available integer, which makes the search in popSmallest very efficient on average.

Algorithm

Initialize a boolean array, isPresent, of a size large enough to cover all possible numbers (e.g., 2002, based on problem constraints). Mark all entries from 1 upwards as true.
Initialize an integer pointer, smallestPtr, to 1.
For popSmallest():
- Use a while loop to advance smallestPtr until it points to an index i where isPresent[i] is true.
- This smallestPtr is the smallest number. Mark isPresent[smallestPtr] as false.
- Return the value of smallestPtr.
For addBack(num):
- Mark isPresent[num] as true.
- As an optimization, if num is smaller than smallestPtr, update smallestPtr = num.

Walkthrough

This approach leverages the problem's constraints to use a fixed-size boolean array for O(1) lookups and updates. A pointer smallestPtr is used to efficiently find the next smallest element.

1class SmallestInfiniteSet {2    private boolean[] isPresent;3    private int smallestPtr;4 5    public SmallestInfiniteSet() {6        // Constraints: num <= 1000, 1000 calls.7        // Max number popped could be 1000. Max num added back is 1000.8        // A size of 2002 is safe to handle all possible numbers.9        isPresent = new boolean[2002];10        for (int i = 1; i < isPresent.length; i++) {11            isPresent[i] = true;12        }13        smallestPtr = 1;14    }15    16    public int popSmallest() {17        // Find the first available number starting from smallestPtr.18        // This loop's total work is amortized across all calls.19        while (!isPresent[smallestPtr]) {20            smallestPtr++;21        }22        23        int result = smallestPtr;24        isPresent[result] = false;25        return result;26    }27    28    public void addBack(int num) {29        if (!isPresent[num]) {30            isPresent[num] = true;31            // Optimization: if we add back a number smaller than our current pointer,32            // it becomes the new candidate for the smallest.33            if (num < smallestPtr) {34                smallestPtr = num;35            }36        }37    }38}

Complexity

Time

`popSmallest()`: Amortized O(1). The `smallestPtr` only moves forward. Across all calls, the total work for the search loop is bounded by the maximum number reached, making the amortized cost constant. `addBack()`: O(1).

Space

O(M), where M is the maximum possible value of a number we need to track (e.g., 2002 in this implementation). The space is constant with respect to the number of calls.

Trade-offs

Pros

Extremely fast with O(1) amortized time for popSmallest and O(1) for addBack.
Very simple to understand and implement.

Cons

The solution is not general. It relies on the constraints on the input values (num) and the number of calls to pre-allocate a fixed-size array.
If num could be very large (e.g., 10^9), this approach would be infeasible due to memory limitations.
The space complexity is proportional to the maximum value of num, not the number of operations.

Solutions

Solution

1class SmallestInfiniteSet { private TreeSet < Integer > s = new TreeSet <>(); public SmallestInfiniteSet () { for ( int i = 1 ; i <= 1000 ; ++ i ) { s . add ( i ); } } public int popSmallest () { return s . pollFirst (); } public void addBack ( int num ) { s . add ( num ); } } /** * Your SmallestInfiniteSet object will be instantiated and called as such: * SmallestInfiniteSet obj = new SmallestInfiniteSet(); * int param_1 = obj.popSmallest(); * obj.addBack(num); */

1class SmallestInfiniteSet { public: SmallestInfiniteSet () { for ( int i = 1 ; i <= 1000 ; ++ i ) { s . insert ( i ); } } int popSmallest () { int x = * s . begin (); s . erase ( s . begin ()); return x ; } void addBack ( int num ) { s . insert ( num ); } private: set < int > s ; }; /** * Your SmallestInfiniteSet object will be instantiated and called as such: * SmallestInfiniteSet* obj = new SmallestInfiniteSet(); * int param_1 = obj->popSmallest(); * obj->addBack(num); */

1from sortedcontainers import SortedSet class SmallestInfiniteSet : def __init__ ( self ): self . s = SortedSet ( range ( 1 , 1001 )) def popSmallest ( self ) -> int : x = self . s [ 0 ] self . s . remove ( x ) return x def addBack ( self , num : int ) -> None : self . s . add ( num ) # Your SmallestInfiniteSet object will be instantiated and called as such: # obj = SmallestInfiniteSet() # param_1 = obj.popSmallest() # obj.addBack(num)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem