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
["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.

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;
    }

    public void addBack(int num) {
        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();
 * obj.addBack(num);
 */

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

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

    public SmallestInfiniteSet() {
    }

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

    public void addBack(int num) {
        black.remove(num);
    }
}

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

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

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

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


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

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

# 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()
# obj.addBack(num)

class SmallestInfiniteSet {
public:
    unordered_set<int> black;

    SmallestInfiniteSet() {
    }

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

    void addBack(int num) {
        black.erase(num);
    }
};

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

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();
 * obj.AddBack(num);
 */

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;
    }

    addBack(num: number): void {
        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()
 * obj.addBack(num)
 */

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();
 * obj.add_back(num);
 */

Explain:

nope.

Complexity:

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

2336 - Smallest Number in Infinite Set

2336. Smallest Number in Infinite Set

Problem

Solution (Java, C++, Python)

All Problems

All Solutions

Welcome to Subscribe On Youtube

2336. Smallest Number in Infinite Set

Problem

Solution (Java, C++, Python)

All Problems

All Solutions