Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
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 <= 10001000 calls will be made in total to popSmallest and addBack.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Design · Segment Tree
["SmallestInfiniteSet","addBack","popSmallest","popSmallest","popSmallest","addBack","popSmallest","popSmallest","popSmallest"] [[],[2],[],[],[],[1],[],[],[]]
first-missing-positive)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2336: Smallest Number in Infinite Set
class SmallestInfiniteSet {
private TreeSet<Integer> s = new TreeSet<>();
public SmallestInfiniteSet() {
for (int i = 1; i <= 1000; ++i) {
s.add(i);
}
}
public int popSmallest() {
return s.pollFirst();
}
public void addBack(int num) {
s.add(num);
}
}
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet obj = new SmallestInfiniteSet();
* int param_1 = obj.popSmallest();
* obj.addBack(num);
*/
// Accepted solution for LeetCode #2336: Smallest Number in Infinite Set
type SmallestInfiniteSet struct {
s *treemap.Map
}
func Constructor() SmallestInfiniteSet {
s := treemap.NewWithIntComparator()
for i := 1; i <= 1000; i++ {
s.Put(i, nil)
}
return SmallestInfiniteSet{s}
}
func (this *SmallestInfiniteSet) PopSmallest() int {
x, _ := this.s.Min()
this.s.Remove(x.(int))
return x.(int)
}
func (this *SmallestInfiniteSet) AddBack(num int) {
this.s.Put(num, nil)
}
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.PopSmallest();
* obj.AddBack(num);
*/
# Accepted solution for LeetCode #2336: Smallest Number in Infinite Set
class SmallestInfiniteSet:
def __init__(self):
self.s = SortedSet(range(1, 1001))
def popSmallest(self) -> int:
x = self.s[0]
self.s.remove(x)
return x
def addBack(self, num: int) -> None:
self.s.add(num)
# Your SmallestInfiniteSet object will be instantiated and called as such:
# obj = SmallestInfiniteSet()
# param_1 = obj.popSmallest()
# obj.addBack(num)
// Accepted solution for LeetCode #2336: Smallest Number in Infinite Set
use std::collections::BTreeSet;
struct SmallestInfiniteSet {
s: BTreeSet<i32>,
}
impl SmallestInfiniteSet {
fn new() -> Self {
let mut set = BTreeSet::new();
for i in 1..=1000 {
set.insert(i);
}
SmallestInfiniteSet { s: set }
}
fn pop_smallest(&mut self) -> i32 {
let x = *self.s.iter().next().unwrap();
self.s.remove(&x);
x
}
fn add_back(&mut self, num: i32) {
self.s.insert(num);
}
}
// Accepted solution for LeetCode #2336: Smallest Number in Infinite Set
class SmallestInfiniteSet {
private pq = new MinPriorityQueue<number>();
private s = new Set<number>();
constructor() {
for (let i = 1; i <= 1000; i++) {
this.pq.enqueue(i);
this.s.add(i);
}
}
popSmallest(): number {
const x = this.pq.dequeue();
this.s.delete(x);
return x;
}
addBack(num: number): void {
if (!this.s.has(num)) {
this.pq.enqueue(num);
this.s.add(num);
}
}
}
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* var obj = new SmallestInfiniteSet()
* var param_1 = obj.popSmallest()
* obj.addBack(num)
*/
Use this to step through a reusable interview workflow for this problem.
Use a simple list or array for storage. Each operation (get, put, remove) requires a linear scan to find the target element — O(n) per operation. Space is O(n) to store the data. The linear search makes this impractical for frequent operations.
Design problems target O(1) amortized per operation by combining data structures (hash map + doubly-linked list for LRU, stack + min-tracking for MinStack). Space is always at least O(n) to store the data. The challenge is achieving constant-time operations through clever structure composition.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.