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.

Learn more about Heap (Priority Queue) patterns.

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.

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.

Solution Implementation

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

Learn more about how to find time and space complexity quickly using problem constraints.