{x}
blog image

Smallest Number in Infinite Set

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 Explanation: Smallest Number in Infinite Set

This problem requires designing a data structure that efficiently handles adding and removing the smallest element from a set of positive integers. While the set is conceptually infinite, the problem constrains the input numbers to the range [1, 1000], making certain approaches feasible.

Approach 1: Ordered Set (TreeSet/SortedSet)

This approach leverages the properties of an ordered set (like TreeSet in Java or SortedSet in Python) to maintain the elements in sorted order. This directly facilitates finding and removing the smallest element.

Algorithm:

  1. Initialization: The constructor creates an ordered set and populates it with integers from 1 to 1000. This takes O(n log n) time, where n is the maximum number (1000 in this case).

  2. popSmallest(): This method simply retrieves and removes the smallest element (the first element) from the ordered set. This operation takes O(log n) time due to the efficient implementation of ordered sets.

  3. addBack(num): This method inserts the given number num back into the ordered set. Again, this takes O(log n) time because of the efficient insertion in an ordered set. The check for whether the number is already present is implicitly handled by the ordered set's unique element constraint.

Time Complexity:

  • Initialization: O(n log n)
  • popSmallest(): O(log n)
  • addBack(): O(log n)

Space Complexity: O(n) to store the set of numbers.

Approach 2: Min-Heap (Priority Queue) + Set

This approach uses a combination of a min-heap (priority queue) and a set.

Algorithm:

  1. Initialization: A min-heap is created and populated with numbers 1 to 1000. The heap maintains the smallest element at the top, allowing O(1) access to it. A set is also used to track which elements are currently in the data structure. The initialization is O(n log n).

  2. popSmallest(): The dequeue() operation on the min-heap retrieves and removes the smallest element in O(log n) time. The set is updated accordingly.

  3. addBack(num): The method first checks if the number is already present in the set. If not, it enqueues the number to the min-heap and updates the set. This takes O(log n) time for heap enqueue.

Time Complexity:

  • Initialization: O(n log n)
  • popSmallest(): O(log n)
  • addBack(): O(log n)

Space Complexity: O(n) to store the heap and set.

Code Examples (Python - Approach 1, TypeScript - Approach 2)

Python (Approach 1):

import bisect
 
class SmallestInfiniteSet:
    def __init__(self):
        self.s = list(range(1, 1001))
 
    def popSmallest(self) -> int:
        x = self.s.pop(0)
        return x
 
    def addBack(self, num: int) -> None:
        if num not in self.s:
            bisect.insort(self.s, num)

TypeScript (Approach 2): (Requires a MinPriorityQueue implementation; several are available on npm)

// ... (MinPriorityQueue implementation needed here) ...
 
class SmallestInfiniteSet {
    // ... (Implementation as described in the detailed explanation) ...
}

Note: The provided TypeScript solution uses a custom TreeSet implementation for the ordered set approach. For the min-heap approach, a library like priority-queue would be necessary. Other languages will have equivalent data structures and libraries to implement both approaches efficiently.