Smallest Infinite Set
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
operations = ["SmallestInfiniteSet", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest"][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
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. When popping, if the heap is non-empty, pop from it (since it contains smaller numbers added back); otherwise, pop the next smallest number from the pointer and increment it. Adding back a number means pushing it into the heap only if it is smaller than the pointer and not already in the heap, ensuring no duplicates.
Optimal Approach
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.
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.
Pattern Spotlight
Heaps (Dynamic Minimum Tracking with Auxiliary Set)
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.
Solution
| 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) |
Step-by-Step Solution
Initialize the Next Smallest Pointer, Min-Heap, and Membership Set
| 5 | self.next_smallest = 1 |
| 6 | self.heap = [] |
| 7 | self.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.
Pop the Smallest Number by Prioritizing Added-Back Heap Elements
| 10 | if self.heap: |
| 11 | num = heapq.heappop(self.heap) |
| 12 | self.in_heap.remove(num) |
| 13 | return num |
| 15 | num = self.next_smallest |
| 16 | self.next_smallest += 1 |
| 17 | return num |
Objective
To return and remove the smallest number from the data structure, prioritizing numbers in the heap before advancing the next smallest pointer.
Key Insight
If the heap is non-empty, the smallest added-back number must be popped first because it is smaller than the current 'next_smallest'. Removing it from the heap and membership set maintains consistency. If the heap is empty, the 'next_smallest' pointer is returned and incremented, representing the next number in the infinite sequence. This dual-source approach efficiently manages the infinite conceptual set with finite data structures.
Interview Quick-Check
Core Logic
popSmallest returns the smallest number from the heap if available, otherwise returns 'next_smallest' and increments it, ensuring correct ordering.
State & Boundaries
Removing the popped number from 'in_heap' ensures the heap membership set remains accurate.
Common Pitfalls & Bugs
Failing to remove the popped number from the membership set leads to incorrect duplicate prevention in addBack.
Add Back a Number Only if It Is Smaller Than Next Smallest and Not Already Present
| 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) |
Objective
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.
Key Insight
Numbers greater or equal to 'next_smallest' are implicitly present in the infinite set and do not need to be added back explicitly. Adding only smaller numbers ensures the heap contains only those numbers that were popped and are now candidates to be popped again before 'next_smallest'. Checking membership prevents duplicates, preserving heap integrity and correctness.
Interview Quick-Check
Core Logic
addBack pushes the number into the heap and membership set only if it is smaller than 'next_smallest' and not already present, maintaining correctness.
Common Pitfalls & Bugs
Adding numbers greater or equal to 'next_smallest' would cause duplicates and incorrect behavior.
State & Boundaries
Membership check prevents duplicate entries in the heap, which is essential for correctness.
Line Analysis
This solution has 7 Critical lines interviewers watch for.
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.
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.
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.
self.in_heap = set()Initialize a set to track membership of numbers in the heap.
The set prevents duplicates in the heap, which is critical for correctness and efficiency.
self.in_heap.remove(num)Remove the popped number from the membership set.
Maintains consistency between the heap and membership set, preventing stale entries and ensuring correctness of addBack.
heapq.heappush(self.heap, num)Push the number into the min-heap.
Adds the number back into the candidate pool for popping, maintaining heap order for efficient retrieval.
self.in_heap.add(num)Add the number to the membership set.
Tracks the presence of the number in the heap to prevent duplicates and maintain correctness.
self.next_smallest = 1Initialize the pointer to the next smallest number to pop, starting at 1.
This pointer tracks the smallest number not yet popped or added back, enabling efficient retrieval without storing the entire infinite set.
return numReturn the popped number from the heap.
Completes the popSmallest operation by returning the smallest available number from the added-back set.
num = self.next_smallestAssign the current next smallest number to be returned.
When the heap is empty, the next smallest number is the pointer value, representing the smallest number never popped or added back.
self.next_smallest += 1Increment the next smallest pointer for future pops.
Advances the pointer to the next number in the infinite sequence, maintaining correctness of the infinite set abstraction.
return numReturn the next smallest number from the infinite sequence.
Completes the popSmallest operation when no added-back numbers are available.
if self.heap:Check if the heap contains any added-back numbers.
Determines whether to pop from the heap or return the next smallest number from the infinite sequence.
Test Your Understanding
Why is it necessary to maintain both a min-heap and a set for the added-back numbers?
The min-heap efficiently retrieves the smallest added-back number, but it does not prevent duplicates. The set tracks membership to avoid pushing duplicates into the heap, ensuring correctness and preventing redundant entries.
Related Problems
Heaps pattern
Don't just read it. Drill it.
Reconstruct Smallest 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 Infinite Set drill