Is Smallest Number in Infinite Set easy or hard?

Smallest Number in Infinite Set is classified as a Medium problem. The difficulty comes from designing a data structure that efficiently supports two operations while preserving ordering. Understanding heaps and state tracking makes the implementation straightforward.

Smallest Number in Infinite Set Python/Java solution

In Python, the solution typically uses heapq for the priority queue and a set for membership tracking. In Java, developers use PriorityQueue with a HashSet. Both implementations maintain a pointer for the next unused integer and achieve O(log n) operations.

How to solve Smallest Number in Infinite Set in O(n)?

An indexed array with boolean flags can simulate the infinite set when operation limits are small. Maintain a pointer to the smallest available index and move it forward when numbers are popped. addBack simply marks the index available again. Each index is processed at most once, giving O(1) amortized operations with O(n) space.

What is the best approach for Smallest Number in Infinite Set?

The most reliable approach uses a min-heap (priority queue) combined with a hash set. A pointer tracks the smallest number never removed from the infinite sequence, while the heap stores numbers added back. popSmallest runs in O(log n) when the heap is used, and addBack also costs O(log n). This design cleanly handles dynamic reinsertion.

Is Smallest Number in Infinite Set asked at Google/Amazon/Meta?

Design-style data structure problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The problem tests heap usage, state management, and handling of dynamic insertions, which are common interview themes.

What data structure is used in Smallest Number in Infinite Set?

The optimal solution combines a min-heap (priority queue) with a hash set. The heap keeps reinserted numbers ordered so the smallest can be retrieved quickly, while the hash set prevents duplicates and supports O(1) membership checks.

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

Using the priority queue + hash set design, both popSmallest and addBack run in O(log n) time due to heap operations. Hash set lookups are O(1). Space complexity is O(n) for the stored numbers that were removed and later reinserted.

Description Hints 2 Solution Video 31:08

2336. Smallest Number in Infinite Set

Medium70.6% acceptance6 companies

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: