##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2336.html

# 2336. Smallest Number in Infinite Set

• Difficulty: Medium.
• Related Topics: Hash Table, Design, Heap (Priority Queue).
• Similar Questions: First Missing Positive.

## 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
[[], [2], [], [], [], [1], [], [], []]
Output
[null, null, 1, 2, 3, null, 1, 4, 5]

Explanation
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
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.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.

## Solution (Java, C++, Python)

• class SmallestInfiniteSet {
private int[] set = new int[1001];
private int ptr = 1;

public SmallestInfiniteSet() {
for (int i = 1; i <= 1000; i++) {
set[i] = 1;
}
}

public int popSmallest() {
int val = -1;
if (ptr > 0 && ptr <= 1000) {
set[ptr] = 0;
val = ptr++;
while (ptr <= 1000 && set[ptr] == 0) {
ptr++;
}
}
return val;
}

if (set[num] == 0) {
set[num] = 1;
if (num < ptr) {
ptr = num;
}
}
}
}

/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet obj = new SmallestInfiniteSet();
* int param_1 = obj.popSmallest();
*/

############

class SmallestInfiniteSet {
private Set<Integer> black = new HashSet<>();

public SmallestInfiniteSet() {
}

public int popSmallest() {
int i = 1;
for (; black.contains(i); ++i)
;
return i;
}

black.remove(num);
}
}

/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet obj = new SmallestInfiniteSet();
* int param_1 = obj.popSmallest();
*/

• class SmallestInfiniteSet:
def __init__(self):
self.black = set()

def popSmallest(self) -> int:
i = 1
while i in self.black:
i += 1
return i

def addBack(self, num: int) -> None:

# Your SmallestInfiniteSet object will be instantiated and called as such:
# obj = SmallestInfiniteSet()
# param_1 = obj.popSmallest()

############

# 2336. Smallest Number in Infinite Set
# https://leetcode.com/problems/smallest-number-in-infinite-set/

class SmallestInfiniteSet:

def __init__(self):
self.A = [True] * (1001)
self.index = 1

def popSmallest(self) -> int:
res = 0

for i in range(1, len(self.A)):
if self.A[i]:
res = i
self.A[i] = False
break

return res

def addBack(self, num: int) -> None:
self.A[num] = True

# Your SmallestInfiniteSet object will be instantiated and called as such:
# obj = SmallestInfiniteSet()
# param_1 = obj.popSmallest()


• class SmallestInfiniteSet {
public:
unordered_set<int> black;

SmallestInfiniteSet() {
}

int popSmallest() {
int i = 1;
for (; black.count(i); ++i)
;
black.insert(i);
return i;
}

black.erase(num);
}
};

/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet* obj = new SmallestInfiniteSet();
* int param_1 = obj->popSmallest();
*/

• type SmallestInfiniteSet struct {
black map[int]bool
}

func Constructor() SmallestInfiniteSet {
s := map[int]bool{}
return SmallestInfiniteSet{s}
}

func (this *SmallestInfiniteSet) PopSmallest() int {
i := 1
for ; this.black[i]; i++ {
}
this.black[i] = true
return i
}

func (this *SmallestInfiniteSet) AddBack(num int) {
this.black[num] = false
}

/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.PopSmallest();
*/

• class SmallestInfiniteSet {
private hashMap: boolean[];

constructor() {
this.hashMap = new Array(1001).fill(true);
}

popSmallest(): number {
for (let i = 1; i <= 1001; i++) {
if (this.hashMap[i]) {
this.hashMap[i] = false;
return i;
}
}
return -1;
}

if (!this.hashMap[num]) {
this.hashMap[num] = true;
}
}
}

/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* var obj = new SmallestInfiniteSet()
* var param_1 = obj.popSmallest()
*/


• struct SmallestInfiniteSet {
counter: [bool; 1000]
}

/**
* &self means the method takes an immutable reference.
* If you need a mutable reference, change it to &mut self instead.
*/
impl SmallestInfiniteSet {

fn new() -> Self {
Self {
counter: [true; 1000]
}
}

fn pop_smallest(&mut self) -> i32 {
for i in 0..1000 {
if self.counter[i] {
self.counter[i] = false;
return i as i32 + 1;
}
}
-1
}

fn add_back(&mut self, num: i32) {
self.counter[num as usize - 1] = true;
}
}

/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* let obj = SmallestInfiniteSet::new();
* let ret_1: i32 = obj.pop_smallest();
*/


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).