2336.Smallest_Number_in_Infinite_Set(Medium).md

2336. Smallest Number in Infinite Set (Medium)

Date and Time: Nov 9, 2024, 23:22 (EST)

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

Question:

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.

Walk-through:

1. Python Intuitive Solution

The first add 1000 elements into a minHeap and create a set() to keep track of elements we add. When we call popSmallest(), we remove the top element from minHeap and set(), then return this val. When we call addBack(), we first check this num is not in set(), then we add it back to set() and heappush() to minHeap.

2. Python Optimized Solution:

We can optimze by using a variable to keep track of current smallest integer we have starting from 1 when minHeap is empty. When minHeap is empty, we increment self.smallest += 1 and return self.smallest - 1. If it is not empty, we return the top of minHeap and remove the set(). We addBack() if we know num < self.smallest and this num not in self.set.

Python Intuitive Solution:

class SmallestInfiniteSet:
    # Maintain a minHeap from 1 to 1000
    # Use set() to keep track of elem to avoid adding duplicate elem into minHeap
    
    # TC: O(n), n = 1000, SC: O(n)
    def __init__(self):
        self.set = set()
        self.minHeap = []
        for i in range(1, 1001):
            heapq.heappush(self.minHeap, i)
            self.set.add(i)

    # O(log n) to heappop
    def popSmallest(self) -> int:
        # Remove this element from minHeap and remove from set()
        val = heapq.heappop(self.minHeap)
        self.set.remove(val)
        return val

    # O(log n) to heappush
    def addBack(self, num: int) -> None:
        if num not in self.set:
            self.set.add(num)
            heapq.heappush(self.minHeap, num)

Time Complexity: $O(n)$, n is 1000 elements we added.
Space Complexity: $O(n)$

Python Solution:

class SmallestInfiniteSet:
    # Use default var smallest from 1 to keep track of current smallest element, if we have not added anything to minHeap[]
    
    # TC: O(log n), n is # elements in heap, SC: O(n)
    def __init__(self):
        self.smallest = 1
        self.minHeap = []
        self.set = set()
    
    # O(log n) for heappop()
    def popSmallest(self) -> int:
        # When minHeap is not empty, we can pop from minHeap
        if self.minHeap:
            self.set.remove(self.minHeap[0])
            return heapq.heappop(self.minHeap)
        # If minHeap is empty, we increment smallest
        self.smallest += 1
        return self.smallest - 1

    # O(log n) for heappush()
    def addBack(self, num: int) -> None:
        # Only add num when it is smaller than self.smallest and not in set()
        if num < self.smallest and num not in self.set:
            self.set.add(num)
            heapq.heappush(self.minHeap, num)

Time Complexity: $O(log\ n)$, n is number of elements in heap.
Space Complexity: $O(n)$