How do you solve Smallest Number in Infinite Set?

Use a min-heap to store added-back numbers and a set to track membership in the heap. Maintain a pointer 'next_smallest' for the smallest number not yet popped. popSmallest() returns the smallest number from the heap if available; otherwise, returns 'next_smallest' and increments it. addBack(num) pushes 'num' into the heap and set only if 'num' is smaller than 'next_smallest' and not already in the heap. This approach guarantees O(log n) operations and handles the infinite conceptual set efficiently.

What pattern does Smallest Number in Infinite Set use?

The Pattern: Heaps (Dynamic Minimum Tracking with Auxiliary Set) The Heuristic: When managing a dynamic set with insertions and removals where the smallest element must be retrieved efficiently, use a min-heap combined with a membership set to track and retrieve the minimum in O(log n) time while avoiding duplicates.

Smallest Number in Infinite Set | Heaps

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

O(log n) per operation. Each popSmallest operation either pops from the heap or returns the next smallest number in O(1). Popping from the heap costs O(log n) in the worst case. addBack operations push into the heap and set in O(log n). Since the heap size is at most the number of added-back elements, operations remain efficient.

Problem

Implement a data structure that initially contains all positive integers and supports operations to pop the smallest number and add back numbers that were previously popped.

1 ≤ num ≤ 1000
At most 1000 calls will be made to popSmallest and addBack.

Example

Input: operations = ["SmallestInfiniteSet", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest"]

Output: [null, 1, 2, null, 2, 3]

Initially, the set contains all positive integers starting from 1. The first popSmallest() returns 1 and removes it. The second popSmallest() returns 2 and removes it. The addBack(2) adds 2 back into the set because it is smaller than the next smallest number (which is 3). The next popSmallest() returns 2 again, removing it. The following popSmallest() returns 3.

Approach

Straightforward Solution

A naive approach would maintain a sorted list of all numbers, but this is impossible due to infinite size. Alternatively, tracking all popped numbers and searching for the smallest missing number each time would be inefficient.

Core Observation

The set conceptually contains an infinite sequence of positive integers starting from 1, but only a finite subset is ever removed or added back. The smallest number to pop is either the smallest number not yet popped (tracked by a counter) or a previously popped number that was added back.

Path to Optimal

Preview

The key insight is to maintain a pointer to the next smallest number not yet popped and a min-heap to store numbers that have been added back…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a min-heap to store added-back numbers and a set to track membership in the heap. Maintain a pointer 'next_smallest' for the smallest number not yet popped…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(log n) per operation

Each popSmallest operation either pops from the heap or returns the next smallest number in O(1). Popping from the heap costs O(log n) in the worst case. addBack operations push into the heap and set in O(log n). Since the heap size is at most the number of added-back elements, operations remain efficient.

Space

O(n)

The heap and set store at most all numbers that have been added back, which is bounded by the number of operations, making space usage linear in the number of addBack calls.

Solution

Python

1import heapq
2
3class SmallestInfiniteSet:
  def __init__(self):
      self.next_smallest = 1
      self.heap = []
      self.in_heap = set()
8
  def popSmallest(self) -> int:
      if self.heap:
          num = heapq.heappop(self.heap)
          self.in_heap.remove(num)
          return num
14
      num = self.next_smallest
      self.next_smallest += 1
      return num
18
  def addBack(self, num: int) -> None:
      if num < self.next_smallest and num not in self.in_heap:
          heapq.heappush(self.heap, num)
          self.in_heap.add(num)

Step-by-Step Solution

1

Initialize the Next Smallest Pointer, Min-Heap, and Membership Set

5self.next_smallest = 1
6self.heap = []
7self.in_heap = set()

Objective

To set up the initial state with the next smallest number to pop, an empty min-heap for added-back numbers, and a set to track heap membership.

Key Insight

The 'next_smallest' pointer represents the smallest number not yet popped or added back, allowing O(1) retrieval when the heap is empty. The min-heap stores numbers added back that are smaller than 'next_smallest', enabling efficient retrieval of the smallest added-back number. The set prevents duplicates in the heap, maintaining correctness and efficiency.

Interview Quick-Check

Core Logic

The 'next_smallest' pointer tracks the smallest number never popped or added back, enabling constant-time retrieval when the heap is empty.

Core Logic

The min-heap stores added-back numbers smaller than 'next_smallest', ensuring the smallest number is always accessible.

State & Boundaries

The set 'in_heap' prevents duplicates in the heap, which is critical for correctness and avoiding redundant work.

2

Pop the Smallest Number by Prioritizing Added-Back Heap Elements

To return and remove the smallest number from the data structure, prioritizing numbers in the heap before advancing the next smallest pointer.

3

Add Back a Number Only if It Is Smaller Than Next Smallest and Not Already Present

To reinsert a previously popped number into the data structure only if it is smaller than the current 'next_smallest' and not already in the heap.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 7 Critical lines interviewers watch for.

Line 11 Critical

num = heapq.heappop(self.heap)

Pop the smallest number from the heap.

Retrieves the smallest added-back number in O(log n) time, ensuring correct ordering of popped numbers.

Line 20 Critical

if num < self.next_smallest and num not in self.in_heap:

Check if the number to add back is smaller than next smallest and not already in the heap.

Ensures only numbers that have been popped and are smaller than the current pointer are added back, preventing duplicates and preserving the infinite set abstraction.

Line 6 Critical

self.heap = []

Initialize an empty min-heap to store numbers added back.

The min-heap efficiently maintains the smallest added-back numbers, allowing O(log n) insertion and removal.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why is it necessary to maintain both a min-heap and a set for the added-back numbers?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Smallest Number in Infinite Set from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Smallest Number in Infinite Set drill

or drill a free problem

1	`import heapq`
2
3	`class SmallestInfiniteSet:`
4	`def __init__(self):`
5	`self.next_smallest = 1`
6	`self.heap = []`
7	`self.in_heap = set()`
8
9	`def popSmallest(self) -> int:`
10	`if self.heap:`
11	`num = heapq.heappop(self.heap)`
12	`self.in_heap.remove(num)`
13	`return num`
14
15	`num = self.next_smallest`
16	`self.next_smallest += 1`
17	`return num`
18
19	`def addBack(self, num: int) -> None:`
20	`if num < self.next_smallest and num not in self.in_heap:`
21	`heapq.heappush(self.heap, num)`
22	`self.in_heap.add(num)`