Skip to main content
Talentd

Smallest Number in Infinite Set - Solution & Explanation

MediumHash TableDesignHeap (Priority Queue)Ordered Set21 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You design a data structure that represents an infinite set of positive integers starting from 1. The structure must support two operations: popSmallest(), which removes and returns the smallest available number, and addBack(num), which inserts a previously removed number back into the set.

Approach 1: Priority Queue + Hash Set (O(log n) per operation)

This approach explicitly tracks numbers that were removed and later reinserted. Maintain a min-heap storing values returned through addBack and a hash set to avoid duplicates. Also keep a pointer current representing the smallest number that has never been popped from the infinite sequence. When popSmallest() runs, compare the heap's smallest element with current. If the heap contains a smaller value, remove it from the heap and set; otherwise return current and increment the pointer. When addBack(num) is called, insert num into the heap only if it is smaller than current and not already tracked in the set. Heap operations cost O(log n) time and the set ensures constant-time membership checks. Space complexity is O(n) for stored reinserted values. This design is a classic combination of heap (priority queue) ordering with fast lookups using a hash table.

Approach 2: Indexed Array with Flags (O(1) amortized)

Because the number of operations is bounded, you can simulate the infinite set using a boolean array that tracks whether a number has been removed or added back. Maintain a pointer pointing to the current smallest candidate. When popSmallest() runs, move the pointer forward until you find an index marked available, mark it removed, and return it. For addBack(num), simply flip the flag back to available if the number was previously removed. Each element is scanned at most once during pointer advancement, giving O(1) amortized time for popSmallest() and O(1) for addBack(). Space complexity is O(n) for the flag array. This approach works well when operation limits are small and avoids the overhead of heap operations or maintaining an ordered set.

Recommended for interviews: The priority queue + set approach is the one most interviewers expect. It models the infinite sequence cleanly using a pointer and handles reinserted values efficiently with heap ordering. Implementing it shows you understand heap behavior, duplicate prevention, and state management in a design-style problem. The indexed array method is simpler but depends on constraints; it demonstrates optimization awareness once the baseline design is clear.

Approach 1: Approach using Priority Queue and Set

Using Priority Queue and HashSet

In this approach, we keep track of removed numbers using a priority queue (min heap) and a set to allow efficient look-up, addition, and removal operations. The priority queue keeps the numbers in sorted order, allowing us to quickly access and remove the smallest number. The set helps us to efficiently check whether a number needs to be added back.

Explanation

The implementation uses a min-heap (priority queue) to keep numbers in sorted order. We have a boolean array, present[], to keep track of numbers currently in the heap.

  • For popping the smallest element, we remove the min element from the heap which takes O(log n) time.
  • For adding a back a number, we add it back to the heap only if it was not already present. This takes O(log n) time.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n) for both pop and add operations, where n is the size of the heap.

Space Complexity: O(n), where n is the size of the heap.

Try this approach in the editor →

Approach 2: Approach using Indexed Array and Flags

Using Indexed Array and Flags

In this methodology, we use an integer array to monitor the appearance of each number and a boolean flag array to verify if a number is within the set. This leverages more direct array manipulations without complex data structures.

Explanation

This approach leverages direct manipulations with an array marked as a flag to represent the presence of a number.

  • Using a boolean array ensures tracking availability of each integer.
  • The 'smallest' variable quickly adjusts the potential smallest number to pop next.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1) for addBack(), O(1) for popSmallest() in average case due to direct access using index.

Space Complexity: O(n), trials with fixed space that holds states up to MAX integers.

Try this approach in the editor →

Approach 3: Ordered Set + Simulation

We note that the range of elements in the set given by the problem is [1, 1000], and the operations we need to support are:

  • popSmallest: Pop the smallest element from the set
  • addBack: Add an element back to the set

Therefore, we can use an ordered set to simulate this. Let's denote the ordered set as s, and the elements in the set as s_1, s_2, cdots, s_n, where n is the number of elements in the ordered set. In this problem, n \le 1000.

During initialization, we add all elements in [1, 1000] to the ordered set. The time complexity is O(n times log n).

In the popSmallest operation, we just need to pop the first element from the ordered set. The time complexity for a single operation is O(log n).

In the addBack operation, we just need to add the element back to the ordered set. The time complexity for a single operation is O(log n).

The space complexity is O(n).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach using Priority Queue and Set

Time Complexity: O(log n) for both pop and add operations, where n is the size of the heap.

Space Complexity: O(n), where n is the size of the heap.

Approach using Indexed Array and Flags

Time Complexity: O(1) for addBack(), O(1) for popSmallest() in average case due to direct access using index.

Space Complexity: O(n), trials with fixed space that holds states up to MAX integers.

Ordered Set + Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Priority Queue + Hash SetO(log n) per operationO(n)General solution for design interviews where numbers can be reinserted dynamically
Indexed Array with FlagsO(1) amortizedO(n)When operation limits are small and a bounded simulation of the infinite set is acceptable

Video Solution

Smallest Number in Infinite Set | 3 Approaches | (MICROSOFT) | Leetcode 2336 | Live Code 🧑🏻‍💻 • codestorywithMIK • 9,284 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Smallest Number in Infinite Set with our built-in code editor and test cases.

Practice on FleetCode
Previous

First Missing Positive