# Smallest Number in Infinite Set

### **Problem Statement:-**

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.
    

**Link:** [https://leetcode.com/problems/smallest-number-in-infinite-set/description/](https://leetcode.com/problems/smallest-number-in-infinite-set/description/)

### **Problem Explanation with examples:-**

**Example 1**

```markdown
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`.
    

### Intuition:-

* We will use a dictionary to keep track of the numbers that have been popped.
    
* Another variable will keep track of the smallest number that has not been popped.
    
* When we pop the smallest number, we will add it to the dictionary and increment the smallest number that has not been popped.
    
* When we add a number back, we will remove it from the dictionary and update the smallest number that has not been popped if the number is smaller than the smallest number that has not been popped.
    

### Solution:-

* Create a dictionary and a variable to keep track of the smallest number that has not been popped.
    
* When we pop the smallest number, we will add it to the dictionary and increment the smallest number till we find a number that has not been popped using a while loop.
    
* When we add a number back, we will remove it from the dictionary and update the smallest number that has not been popped if the number is smaller than the smallest number that has not been popped.
    

### Code:-

JAVA Solution

```java
import java.util.HashMap;

class SmallestInfiniteSet {
    private HashMap<Integer, Integer> mp;
    private int sm;

    public SmallestInfiniteSet() {
        mp = new HashMap<>();
        sm = 1;
    }

    public int popSmallest() {
        mp.put(sm, 1);
        int x = sm;
        while (mp.getOrDefault(sm, 0) != 0) {
            sm++;
        }
        return x;
    }

    public void addBack(int num) {
        if (mp.getOrDefault(num, 0) != 0) {
            mp.put(num, 0);
            if (sm > num) {
                sm = num;
            }
        }
    }
}
```

Python Solution

```python
class SmallestInfiniteSet:

    def __init__(self):
        self.mp = {}
        self.sm = 1

    def popSmallest(self) -> int:
        self.mp[self.sm] = 1
        x = self.sm
        while self.mp.get(self.sm,0) != 0:
            self.sm += 1
        return x

    def addBack(self, num: int) -> None:
        if self.mp.get(num,0) != 0:
            self.mp[num] = 0
            if self.sm > num:
                self.sm = num
```

### Complexity Analysis:-

**TIME**:-

The time complexity of the code is **O(1)** for both popSmallest and addBack as we are just doing constant time operations.

**SPACE**:-

The space complexity of the code is **O(n)** where n is the number of elements that have been popped as we are using a dictionary to keep track of the popped elements.

### References:-

* [**Dictionary in Python**](https://www.w3schools.com/python/python_dictionaries.asp)
    
* [**Hashmap in JAVA**](https://www.w3schools.com/java/java_hashmap.asp)
    

### Connect with me:-

* [**Twitter**](https://twitter.com/lakshit_cs)
    
* [**Github**](https://github.com/Lakshit-Chiranjiv)
    
* [**LinkedIn**](https://www.linkedin.com/in/lakshit-chiranjiv-sagar-4b0b15198/)