# 2336. Smallest Number in Infinite Set

https://leetcode.com/problems/smallest-number-in-infinite-set/

## moral: pay attention to constraints

The constraints say the numbers are between 1 and 1000 (inclusive) and there are at most 1000 operations. So we don't need to populate more than 1000.

https://leetcode.com/problems/smallest-number-in-infinite-set/discuss/2261300/Full-Explanations-or-C%2B%2B-or-Set-or-Easy-To-Understand-or-also-Java-%2B-Python-code

## mine

class SmallestInfiniteSet:

    def __init__(self):
        self.st = deque([1])
        self.set = set([1])
    def popSmallest(self) -> int:
        m = self.st.pop()
        self.set.remove(m)
        if not self.st:
            self.st.append(m+1)
            self.set.add(m+1)
        return m

    def addBack(self, num: int) -> None:
        if num < self.st[-1]:
            self.st.append(num)
            self.set.add(num)
            return
        
        
        # TODO: use bin search
        if num in self.set or num > self.st[0]:
            return
        
        for i,x in enumerate(self.st):
            if x < num:
                break
        self.st.insert(i, num)
        self.set.add(num)
        


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