LeetCode 2336 Smallest Number in Infinite Set – JavaScript

What looks like an infinite-data-structure problem becomes much simpler once we notice that we do not need to store the entire infinite set. In this LeetCode 2336 Smallest Number in Infinite Set solution, we use a JavaScript Set to remember numbers that were added back and a current pointer to represent the untouched part of the infinite sequence.

The key idea is to separate the numbers that have been removed and later returned from the numbers that have never been removed. This lets us simulate the infinite set without actually creating it.

Problem Statement

LeetCode 2336, Smallest Number in Infinite Set, asks us to implement a data structure that initially contains every positive integer:

1, 2, 3, 4, 5, 6, ...

We need to support two operations:

• popSmallest() removes and returns the smallest number currently available.
• addBack(num) adds a number back if it is no longer present in the set.

You can read the original problem on LeetCode 2336 – Smallest Number in Infinite Set .

Problem Number: 2336
Difficulty: Medium
Topics: Set, Design, Heap / Priority Queue

Examples

Example 1

Input:

["SmallestInfiniteSet", "addBack", "popSmallest",
 "popSmallest", "popSmallest", "addBack",
 "popSmallest", "popSmallest", "popSmallest"]

[[], [2], [], [], [], [1], [], [], []]

Output:

[null, null, 1, 2, 3, null, 1, 4, 5]

Calling addBack(2) does nothing because 2 is already present. After removing 1, 2, and 3, calling addBack(1) makes 1 available again, so the next smallest value is 1.

Example 2

Simple sequence:

popSmallest() → 1
popSmallest() → 2
popSmallest() → 3
addBack(2)
popSmallest() → 2
popSmallest() → 4

Once 2 is added back, it becomes smaller than the next untouched number, 4, so it must be returned first.

Constraints

• 1 <= num <= 1000
• At most 1000 calls are made to popSmallest and addBack in total.

These constraints are important. Although the conceptual set is infinite, only a limited number of operations can happen. Therefore, we never need to explicitly store the entire infinite set.

Key observation: After at most 1000 operations, only a limited number of values can have been removed and added back. We can track those exceptional values instead of representing infinity.

Intuition

Imagine the infinite set as two parts:

Numbers added back   |   Untouched numbers

For example, suppose we have already removed 1, 2, 3, and 4.

The next untouched number is 5. We can represent that with:

current = 5

Now suppose addBack(2) is called. We do not need to move current backward. We simply remember that 2 has become available again:

heap = {2}
current = 5

The smallest available number is now 2. After returning 2, the Set becomes empty, so the next call can return current, which is 5.

This is exactly what the two variables in the solution represent:

• current represents the smallest number that has never been removed.
• heap stores numbers that were removed earlier and subsequently added back.

Approach

Brute-Force Idea

One straightforward idea would be to explicitly store many positive integers and repeatedly search for the smallest available value.

The problem is that the set is conceptually infinite. Storing every positive integer is neither necessary nor practical.

We only need to keep track of numbers that differ from the normal increasing sequence.

Step-by-Step Approach

1. Initialize current = 1.
2. Maintain a Set called heap for numbers that have been added back.
3. In popSmallest(), if the Set contains numbers, find its smallest number, remove it, and return it.
4. If the Set is empty, return current and increment it.
5. In addBack(num), only add num when num < current.

Why does the condition num < current work?

Any number greater than or equal to current has not been removed yet. Therefore, it is already present in the infinite set and does not need to be added back.

For example, if current = 5, then 5, 6, 7, 8, ... are already available. Calling addBack(7) would make no difference.

Dry Run

Let's trace the main example while tracking both pieces of state.

Step	Operation	heap	current	Result
1	addBack(2)	{}	1	No change
2	popSmallest()	{}	2	1
3	popSmallest()	{}	3	2
4	popSmallest()	{}	4	3
5	addBack(1)	{1}	4	1 added
6	popSmallest()	{}	4	1
7	popSmallest()	{}	5	4
8	popSmallest()	{}	6	5

Notice the important transition at addBack(1). The current pointer remains at 4 because the untouched sequence still starts from 4. The value 1 is handled separately through the Set.

LeetCode 2336 Smallest Number in Infinite Set Solution in JavaScript

Here is the submitted JavaScript solution exactly as provided:

JavaScript Solution

var SmallestInfiniteSet = function () {

    this.heap = new Set();

    this.current = 1;

};

/**

 * @return {number}

 */

SmallestInfiniteSet.prototype.popSmallest = function () {

    if (this.heap.size > 0) {

        let smallest = Infinity;

        for (let num of this.heap) {

            smallest = Math.min(smallest, num);

        }

        this.heap.delete(smallest);

        return smallest;

    }

    return this.current++;

};

/**

 * @param {number} num

 * @return {void}

 */

SmallestInfiniteSet.prototype.addBack = function (num) {

    if (num < this.current) {

        this.heap.add(num);

    }

};

Code Walkthrough

1. Tracking numbers added back

this.heap = new Set();

Despite its variable name, heap is not a heap. It is a JavaScript Set.

Its purpose is to store numbers that have previously been removed and then added back. The Set also automatically prevents duplicates.

2. Tracking the untouched sequence

this.current = 1;

current starts at 1 because 1 is initially the smallest number.

Whenever there are no added-back numbers waiting in the Set, the next smallest number is simply current.

3. Finding the smallest added-back number

let smallest = Infinity;

for (let num of this.heap) {
    smallest = Math.min(smallest, num);
}

JavaScript's standard Set does not automatically provide the minimum element. Therefore, when the Set contains values, the solution scans through them and keeps the smallest value found.

This is the main reason the actual time complexity of this solution is O(k) for this case, rather than O(log k) as it would be with a real min-heap.

4. Removing the selected number

this.heap.delete(smallest);
return smallest;

Once the smallest added-back number is found, it is removed from the Set because popSmallest() must remove the returned number from the set.

5. Moving through untouched numbers

return this.current++;

If there are no added-back numbers, the next smallest number comes from the untouched sequence.

The post-increment returns the current value and then moves the pointer forward by one.

6. Adding a number back

if (num < this.current) {
    this.heap.add(num);
}

This condition is the key to avoiding unnecessary entries.

If num < current, that number has already been passed by the pointer and therefore could have been removed. It may genuinely need to be added back.

If num >= current, the number is already part of the untouched infinite sequence, so adding it again would not change anything.

Complexity Analysis

Time Complexity

popSmallest() with a non-empty Set: O(k), where k is the number of values currently stored in the Set, because the code scans every value to find the minimum.

popSmallest() with an empty Set: O(1), because it simply returns current and increments it.

addBack(): O(1) average, because JavaScript Set insertion is expected constant time.

With at most 1000 total operations, the maximum Set size is bounded by the problem's operation limit, so this implementation is fast enough for the given constraints.

Space Complexity

O(k), where k is the number of currently stored added-back values. The solution does not store the infinite set itself.

Edge Cases

• Calling addBack() on a number that was never removed: If the number is greater than or equal to current, it is already available, so nothing is added.
• Adding the same number multiple times: JavaScript's Set automatically prevents duplicate entries.
• Multiple numbers added back: The solution scans all values and returns the smallest one.
• Empty Set: When there are no added-back numbers, current supplies the next smallest value.
• Added-back number smaller than current: It must be returned before the untouched sequence because it is smaller than current.

Common Mistakes and Tips

• Do not try to create the infinite set. Track only the part of the state that can change.
• Do not add numbers that are already present. The num < current check handles this.
• Remember that JavaScript Set is not a min-heap. Finding the minimum requires iteration.
• Use Set semantics to handle duplicate add-back operations. A number should not appear multiple times in the stored collection.

FAQ

Why do we need the current pointer?

The pointer represents the smallest positive integer that has never been removed. Instead of storing all untouched numbers, we simply generate them one at a time using current++.

Why does addBack only store numbers smaller than current?

Numbers greater than or equal to current are still part of the untouched infinite sequence. Only numbers below current could have previously been removed and therefore need to be tracked separately.

Is the Set really a heap in this JavaScript solution?

No. The variable is named heap, but its actual type is Set. The code finds the minimum by iterating through the Set, which gives O(k) time for that operation.

Related Problems

• 41. First Missing Positive
• 1942. The Number of the Smallest Unoccupied Chair
• 2336. Smallest Number in Infinite Set
• 902. Numbers At Most N Given Digit Set

Conclusion

The main lesson from this problem is that an infinite data structure does not necessarily require infinite storage. We only need to represent the numbers that have deviated from the normal increasing sequence.

The current pointer handles untouched numbers, while the Set remembers numbers that have been added back. When the Set is non-empty, we search it for the smallest value; otherwise, we continue from current.

This LeetCode 2336 Smallest Number in Infinite Set solution is particularly useful for learning how to represent an infinite sequence with a small amount of state and how a simple Set can be sufficient when the constraints are small.