2336. Smallest Number in Infinite Set


Problem Description

In this LeetCode problem, we are required to implement a class called SmallestInfiniteSet. This class simulates a set that contains all positive integers starting from 1 and extending to infinity. The class has to provide two operations:

  1. popSmallest(): This operation should remove the smallest number currently in the set and return it. The initial call to this method would return 1, the second call would return 2, and so on. After a number is popped, it is no longer present in the set unless it is added back.

  2. addBack(num): This operation allows one to add a number back into the set. However, a number can be added back only if it has been previously popped from the set and is not currently present.

The challenge is to code these operations efficiently, keeping in mind that there can be an infinite number of integers.

Intuition

The solution to this problem relies on maintaining a auxiliary set to keep track of the numbers that have been popped. We can call this auxiliary set "blacklist" or black in the code sample given. When popSmallest() is called, we start from 1 and check if that number is in the black set. If it is not, we pop it (remove and return) and add it to the black set. If it is, we increment the number and check again until we find the smallest number not in the black set.

When addBack() is called with a number argument, we remove it from the black set, which represents adding it back into the set of available numbers to be popped. This is because a number can only be re-added if it has been removed before, and removing from the black will allow popSmallest() to find it again as the smallest available number.

This approach is intuitive in that it treats the infinite set of positive integers as an implicit list that we only modify by noting which elements are currently not in the set (which are in black). It uses set operations which are typically O(1) for existence check and removal, making the operations efficient.

Solution Approach

Let's discuss the implementation details of the SmallestInfiniteSet class and walk through each method provided in the solution:

Initializer __init__(self):

In Python, the __init__ method serves as an initializer or a constructor for a class. It is automatically invoked when a new instance of the class is created.

For our SmallestInfiniteSet class:

1def __init__(self):
2    self.black = set()

This initializer sets up an empty set called self.black. This set will hold all numbers that have been popped and removed from the infinite set of positive integers.

  • Data Structure: set() is used because it allows fast addition, removal, and membership check operations with an average time complexity of O(1).

Method popSmallest(self) -> int:

The popSmallest method is used to pop and return the smallest integer from the infinite set. The pseudo-algorithm for this method is:

  1. Start with i = 1 since 1 is the smallest positive integer.
  2. Increment i while i is in self.black. This is because if i is in self.black, it means that i has been previously popped.
  3. Once an i is found that is not in self.black, add it to self.black and return it.
1def popSmallest(self) -> int:
2    i = 1
3    while i in self.black:
4        i += 1
5    self.black.add(i)
6    return i
  • Algorithm: Linear search to find the smallest integer not in self.black.
  • Pattern Used: Iteration starting from 1 and incrementing until an integer not in self.black is found.

This method ensures that we always return the next smallest number, as per the requirement of the problem.

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

The addBack method is meant to add a number back into the set if it isn't currently in the set:

1def addBack(self, num: int) -> None:
2    self.black.discard(num)
  • Data Structure: We use the discard method of the set, which removes num if present in self.black. This operation does not raise an error even if num is not present.
  • Pattern Used: Conditional removal, letting the set data structure handle the existence check implicitly.

The situation where addBack is called with a number that has never been popped or is already in the set doesn't change the self.black set, as per the problem's instructions.

These methods collectively allow us to efficiently simulate the infinite set operations of popping the smallest element and adding numbers back into the infinite set.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's use a small example to illustrate how the SmallestInfiniteSet class works according to the solution approach. Assume we create an instance of SmallestInfiniteSet and then perform a series of operations:

  1. Call popSmallest() four times.
  2. Call addBack(2).
  3. Call popSmallest() two more times.

Let's go step by step:

Step 1

We first instantiate our SmallestInfiniteSet class. The black set is initialized as empty.

Step 2

We call popSmallest() for the first time. Since black is empty, 1 is not in black and is returned. black is now {1}.

Step 3

We call popSmallest() for the second time. Here i starts at 1 again but since 1 is in black, increment i to 2. Now 2 is not in black, so 2 is returned and black becomes {1, 2}.

Step 4

We call popSmallest() for the third time. i starts at 1, but both 1 and 2 are in black, so we increment i to 3. Three is returned and black becomes {1, 2, 3}.

Step 5

We call popSmallest() for the fourth time. i starts at 1, but numbers 1, 2, and 3 are in black, so we increment i to 4. Four is returned and black becomes {1, 2, 3, 4}.

Step 6

Now, we call addBack(2). This removes 2 from black. Therefore, black is now {1, 3, 4}.

Step 7

We call popSmallest() again. We start at 1, which is in black. We find that 2 is now not in black (because we just added it back), so we return 2, and black becomes {1, 2, 3, 4}.

Step 8

One final call to popSmallest() starts at 1 again, but we must increment until we find 5, which is not in black. We return 5 and black becomes {1, 2, 3, 4, 5}.

This walkthrough exemplifies how an implied infinite set of positive integers can be manipulated using a black set to track which elements have been 'popped' and are not currently available unless added back. By incrementing the minimal candidate and checking against black, we ensure that popSmallest() always returns the smallest available integer, and by using discard in addBack, we maintain an efficient model of this infinite integer set.

Python Solution

1class SmallestInfiniteSet:
2    def __init__(self):
3        # Initialize an empty set to keep track of popped elements
4        self.popped_elements = set()
5
6    def popSmallest(self) -> int:
7        # Starting from 1, find the smallest integer not yet popped
8        smallest = 1
9        while smallest in self.popped_elements:
10            smallest += 1
11        # Add the found integer to the popped elements set
12        self.popped_elements.add(smallest)
13        # Return the smallest integer
14        return smallest
15
16    def addBack(self, num: int) -> None:
17        # If the number is in the popped elements, remove it to make it available again
18        if num in self.popped_elements:
19            self.popped_elements.remove(num)
20        # Note that if the number is not in the popped elements, no action is taken
21
22# Example of how to use the SmallestInfiniteSet class
23# obj = SmallestInfiniteSet() # Instantiate the class
24# param_1 = obj.popSmallest() # Pop the smallest element available
25# obj.addBack(num) # Add back a specific number into the set of available numbers
26

Java Solution

1import java.util.Set;
2import java.util.HashSet;
3
4class SmallestInfiniteSet {
5    // A HashSet to store numbers that have been popped.
6    private Set<Integer> poppedNumbers = new HashSet<>();
7
8    // Constructor 
9    public SmallestInfiniteSet() {
10        // Nothing to initialize since HashSet is already initialized.
11    }
12
13    // Method to pop the smallest number that has not been popped yet.
14    public int popSmallest() {
15        // Starting from 1, as it's the smallest positive integer.
16        int smallest = 1;
17        // Loop over the set to find the smallest non-popped number (the ones not in poppedNumbers).
18        while (poppedNumbers.contains(smallest)) {
19            // If current number is in the set, increase it to check the next one.
20            smallest++;
21        }
22        // Once the smallest number is found, add it to the set to indicate it has been popped.
23        poppedNumbers.add(smallest);
24        // Return the smallest number that hasn't been popped before.
25        return smallest;
26    }
27
28    // Method to add back a number to the set of available numbers.
29    public void addBack(int num) {
30        // Remove the specified number from the set of popped numbers.
31        poppedNumbers.remove(num);
32    }
33}
34
35/**
36 * The SmallestInfiniteSet object will be instantiated and called as follows:
37 * SmallestInfiniteSet obj = new SmallestInfiniteSet();
38 * int param_1 = obj.popSmallest();      // Pops the smallest available number
39 * obj.addBack(num);                     // Adds back a number to the available set
40 */
41

C++ Solution

1#include <unordered_set>
2using namespace std;
3
4// Class representing an infinite set with functionality to get the smallest element and add elements back
5class SmallestInfiniteSet {
6private:
7    // 'removedNumbers' holds all numbers that have been popped from the set
8    unordered_set<int> removedNumbers;
9
10public:
11    SmallestInfiniteSet() {
12        // Constructor does not need to initialize anything for this implementation.
13        // An alternative could be initializing an internal data structure if needed.
14    }
15
16    // Function to pop the smallest number from the set that hasn't been popped yet
17    int popSmallest() {
18        int current = 1; // We start from 1 as it is the smallest possible positive integer for the infinite set
19        // Loop to find the first number that hasn't been removed yet
20        while (removedNumbers.count(current)) {
21            current++; // If current number is in 'removedNumbers', increment and check the next
22        }
23        // Once we find the smallest number not in 'removedNumbers', add it to the set to mark it as removed
24        removedNumbers.insert(current);
25        return current; // Return the smallest number
26    }
27
28    // Function to add back a number to the set, making it available to be popped again
29    void addBack(int num) {
30        // Erase the number from 'removedNumbers' to mark it as not removed
31        removedNumbers.erase(num);
32    }
33};
34
35// Example usage:
36// SmallestInfiniteSet* obj = new SmallestInfiniteSet();
37// int param_1 = obj->popSmallest();
38// obj->addBack(num);
39

Typescript Solution

1// Initialize a variable to store the smallest available numbers,
2// using an array to represent a set of initialized values to true.
3let smallestAvailable: boolean[] = new Array(1001).fill(true);
4
5/**
6 * Retrieves and removes the smallest number available from the set.
7 * @returns {number} The smallest number that was available.
8 */
9function popSmallest(): number {
10    for (let i = 1; i <= 1001; i++) {
11        if (smallestAvailable[i]) {
12            smallestAvailable[i] = false; // Mark the number as unavailable.
13            return i; // Return the number that's now popped out of the set.
14        }
15    }
16    return -1;
17}
18
19/**
20 * Adds a number back into the set if it's not already marked as available.
21 * @param {number} num - The number to add back to the set.
22 */
23function addBack(num: number): void {
24    if (num >= 1 && num <= 1000 && !smallestAvailable[num]) {
25        smallestAvailable[num] = true; // Mark the number as available again.
26    }
27}
28

Time and Space Complexity

The given Python code defines a class SmallestInfiniteSet that maintains a set of integers from which the smallest number can be "popped" (i.e., returned and removed from the set) and to which specific numbers can be "added back" to the set if they have been previously removed.

Time Complexity

  1. popSmallest Method: The time complexity for popSmallest is O(n), where n is the number of consecutive integers starting from 1 that have been added to the black set. In the worst-case scenario, the method iterates through all elements that have been added to the set to find the smallest one that is not in the set.

  2. addBack Method: The time complexity for addBack is O(1). This is because the discard method of a set in Python, which is used to remove an element if it exists in the set, operates in constant time.

Space Complexity

The space complexity of the entire class is O(m), where m is the number of unique elements that have been popped and not added back. The black set will grow as more unique elements are popped and retained in the set. It will not grow larger than the number of elements that have been popped and not added back, hence the space complexity of O(m).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫