# Smallest Number in Infinite Set
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/smallest-number-in-infinite-set)
Canonical: https://scaleengineer.com/dsa/problems/smallest-number-in-infinite-set
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Hash Table, Heap (Priority Queue), Ordered Set
---
## Problem
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
## Using a Min-Heap for Added-Back Numbers
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.
**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.
**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).
### Explanation
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.

```java
import java.util.PriorityQueue;
import java.util.HashSet;

class SmallestInfiniteSet {
    private int currentInteger;
    private PriorityQueue<Integer> minHeap;
    private HashSet<Integer> isAddedBack;

    public SmallestInfiniteSet() {
        currentInteger = 1;
        minHeap = new PriorityQueue<>();
        isAddedBack = new HashSet<>();
    }
    
    public int popSmallest() {
        int result;
        // If the heap has a smaller number than the next in the sequence, pop from the heap.
        if (!minHeap.isEmpty() && minHeap.peek() < currentInteger) {
            result = minHeap.poll();
            isAddedBack.remove(result);
        } else {
            // Otherwise, take the next integer from the main sequence.
            result = currentInteger;
            currentInteger++;
        }
        return result;
    }
    
    public void addBack(int num) {
        // Only add back if the number is smaller than our current sequence pointer
        // and is not already in the heap.
        if (num < currentInteger && !isAddedBack.contains(num)) {
            minHeap.add(num);
            isAddedBack.add(num);
        }
    }
}
```
### 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.

## Using a Boolean Array to Track Presence
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.
**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.
**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.
### Explanation
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.

```java
class SmallestInfiniteSet {
    private boolean[] isPresent;
    private int smallestPtr;

    public SmallestInfiniteSet() {
        // Constraints: num <= 1000, 1000 calls.
        // Max number popped could be 1000. Max num added back is 1000.
        // A size of 2002 is safe to handle all possible numbers.
        isPresent = new boolean[2002];
        for (int i = 1; i < isPresent.length; i++) {
            isPresent[i] = true;
        }
        smallestPtr = 1;
    }
    
    public int popSmallest() {
        // Find the first available number starting from smallestPtr.
        // This loop's total work is amortized across all calls.
        while (!isPresent[smallestPtr]) {
            smallestPtr++;
        }
        
        int result = smallestPtr;
        isPresent[result] = false;
        return result;
    }
    
    public void addBack(int num) {
        if (!isPresent[num]) {
            isPresent[num] = true;
            // Optimization: if we add back a number smaller than our current pointer,
            // it becomes the new candidate for the smallest.
            if (num < smallestPtr) {
                smallestPtr = num;
            }
        }
    }
}
```
### 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`.

# Solutions
### Java

```java
class 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); */
```

### CPP

```cpp
class 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); */
```

### Python

```python
from 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)
```