MediumNo. 2336

Smallest Number in Infinite Set — LeetCode 2336 Python Solution

Topics
Design, Hash Table, Ordered Set, Heap (Priority Queue)
On a study list
LeetCode 75
Reading time
4 min

The problem

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.

Example

Input
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
Output
[null, null, 1, 2, 3, null, 1, 4, 5]
Explanation
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();

Python solution

PythonSolution
class SmallestInfiniteSet:
    def __init__(self):
        self.s = SortedSet(range(1, 1001))

    def popSmallest(self) -> int:
        x = self.s[0]
        self.s.remove(x)
        return x

    def addBack(self, num: int) -> None:
        self.s.add(num)


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

Complexity

Time
O(n × log n)
Space · auxiliary
O(n)

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2336. Smallest Number in Infinite Set is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 2336. Smallest Number in Infinite Set?

LeetCode 2336. Smallest Number in Infinite Set is rated Medium on LeetCode.

What is the time complexity of LeetCode 2336. Smallest Number in Infinite Set?

The Python solution on this page runs in O(n × log n).

What is the space complexity of LeetCode 2336. Smallest Number in Infinite Set?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 2336. Smallest Number in Infinite Set cover?

LeetCode 2336. Smallest Number in Infinite Set is tagged Design, Hash Table, Ordered Set and Heap (Priority Queue) on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.