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

All Problems

All Solutions