LeetCode 2336 - Smallest Number in Infinite Set

The problem asks us to implement a data structure representing an infinite set of positive integers, initially containing all integers starting from 1.

leetcodemediumhash-tabledesignheap-(priority-queue)ordered-set

LeetCode Problem 2336

Difficulty: 🟡 Medium
Topics: Hash Table, Design, Heap (Priority Queue), Ordered Set

Solution

Problem Understanding

The problem asks us to implement a data structure representing an infinite set of positive integers, initially containing all integers starting from 1. We need to provide two main operations: popSmallest, which removes and returns the smallest integer in the set, and addBack, which adds a previously removed integer back into the set if it is not already present. The input consists of sequential calls to these methods, and the output consists of the results of popSmallest calls.

The constraints tell us that num values are small, from 1 to 1000, and that the total number of operations is also limited to 1000. This allows us to use data structures that can handle these ranges efficiently without worrying about unbounded memory, since the set is conceptually infinite but only needs to manage elements that have been popped or added back explicitly. Edge cases to consider include adding back a number that was never popped, popping numbers continuously to grow the "current smallest" beyond the range of numbers we've explicitly tracked, and re-adding numbers multiple times.

Approaches

The brute-force approach would be to maintain a literal infinite set using a dynamically growing array or list and checking for the smallest element every time we pop. While correct in theory, this approach is infeasible because we cannot store an infinite number of elements, and searching for the minimum would be slow.

The optimal approach leverages the observation that we only need to track numbers that have been popped and added back. We can maintain a min-heap for numbers that have been added back so that popSmallest can efficiently retrieve the smallest "available" number. For numbers that have never been popped, we can simply maintain a counter representing the next smallest integer. Using a set in parallel with the heap prevents duplicates from being added back.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per pop O(n) Maintain a full list/set of integers and search for the minimum each time
Optimal O(log k) per pop/addBack O(k) Use a min-heap and set for tracking added-back numbers, with a counter for unseen numbers

Algorithm Walkthrough

  1. Initialize a min-heap and a set to track numbers added back. Also initialize a counter, current, starting at 1 to represent the smallest number not yet popped or added back.
  2. For popSmallest, check if the heap has any numbers. If it does, pop the smallest from the heap, remove it from the set, and return it. Otherwise, return current and increment current by 1.
  3. For addBack, check if the number is less than current and not already in the set. If so, add it to both the set and the min-heap. Ignore numbers already in the set or greater than current.
  4. The heap ensures that we always return the smallest number added back, while the counter ensures that unseen numbers are returned in order.

This works because every number below current has either been popped and is in the heap/set or has been returned already. The heap always keeps track of the next smallest number that was added back, preserving the order.

Python Solution

import heapq

class SmallestInfiniteSet:

    def __init__(self):
        self.current = 1
        self.heap = []
        self.added_back = set()

    def popSmallest(self) -> int:
        if self.heap:
            smallest = heapq.heappop(self.heap)
            self.added_back.remove(smallest)
            return smallest
        else:
            smallest = self.current
            self.current += 1
            return smallest

    def addBack(self, num: int) -> None:
        if num < self.current and num not in self.added_back:
            heapq.heappush(self.heap, num)
            self.added_back.add(num)

The implementation first initializes a counter current to track unseen numbers, a min-heap for added-back numbers, and a set to prevent duplicates. popSmallest returns the heap's smallest number if available or the next unseen number, incrementing the counter. addBack only pushes numbers smaller than current that are not already in the heap/set.

Go Solution

package main

import (
	"container/heap"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

type SmallestInfiniteSet struct {
	current    int
	heap       *IntHeap
	addedBack  map[int]bool
}

func Constructor() SmallestInfiniteSet {
	h := &IntHeap{}
	heap.Init(h)
	return SmallestInfiniteSet{
		current:   1,
		heap:      h,
		addedBack: make(map[int]bool),
	}
}

func (this *SmallestInfiniteSet) PopSmallest() int {
	if this.heap.Len() > 0 {
		smallest := heap.Pop(this.heap).(int)
		delete(this.addedBack, smallest)
		return smallest
	} else {
		smallest := this.current
		this.current++
		return smallest
	}
}

func (this *SmallestInfiniteSet) AddBack(num int) {
	if num < this.current {
		if _, exists := this.addedBack[num]; !exists {
			heap.Push(this.heap, num)
			this.addedBack[num] = true
		}
	}
}

In Go, we define a custom IntHeap to work with the standard heap interface. A map is used to prevent duplicates. The logic mirrors Python, with heap operations ensuring efficient retrieval and a counter tracking unseen numbers.

Worked Examples

Example 1:

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

Operations:

Operation Heap AddedBack Set Current Output
init [] {} 1 -
addBack(2) [2] {2} 1 -
popSmallest [] {} 2 1
popSmallest [] {} 3 2
popSmallest [] {} 4 3
addBack(1) [1] {1} 4 -
popSmallest [] {} 4 1
popSmallest [] {} 5 4
popSmallest [] {} 6 5

Complexity Analysis

Measure Complexity Explanation
Time O(log k) per operation Heap operations for addBack and popSmallest are logarithmic in the number of added-back elements k
Space O(k) Only numbers added back are stored in heap and set, where k is at most the number of operations

The complexity is acceptable because the number of operations is capped at 1000, and k cannot exceed this.

Test Cases

obj = SmallestInfiniteSet()
obj.addBack(2)          # already present, no effect
assert obj.popSmallest() == 1
assert obj.popSmallest() == 2
assert obj.popSmallest() == 3
obj.addBack(1)
assert obj.popSmallest() == 1
assert obj.popSmallest() == 4
assert obj.popSmallest() == 5

# edge test: add back a number already in the set
obj.addBack(6)
assert obj.popSmallest() == 6
obj.addBack(6)          # should have no effect
assert obj.popSmallest() == 7

# edge test: consecutive pops
for i in range(8, 15):
    assert obj.popSmallest() == i
Test Why
Standard example Validates normal sequence of pop and addBack
Add back existing Ensures duplicates are prevented
Consecutive pops Confirms correct increment of current for unseen numbers

Edge Cases

One important edge case is adding back a number that has never been popped or is already greater than current. Our implementation correctly ignores these numbers because they are already effectively in the set. Another edge case is popping repeatedly until current becomes large; the counter ensures we do not need to store all unseen numbers explicitly. Finally, adding back the same number multiple times tests that our set prevents duplicates, which is handled via the addedBack set in both Python and Go implementations. These cases ensure correctness under all allowed operations.