LeetCode75-2336-Smallest-Number-in-Infinite-Set

🧠 Summary of Thoughts

Key Insight

We do NOT store the infinite set explicitly. Instead, we simulate it using:

• A pointer next → tracks the smallest number that has never been removed
• A min heap → stores numbers that were removed and later added back
• A set → avoids duplicates in the heap

Two Methods

1. popSmallest():

• If heap is not empty → return the smallest element from heap
• Otherwise → return next and increment it

2. addBack(num):

   Only add num to heap if:

   • num < next (it was removed before) and it is not already in heap

✅ Code（Java）

class SmallestInfiniteSet {
    private int next;
    private PriorityQueue<Integer> minHeap;
    private Set<Integer> set;
    public SmallestInfiniteSet() {
        next = 1;
        minHeap = new PriorityQueue<>();
        set = new HashSet<>();
    }
    
    public int popSmallest() {
        if(!minHeap.isEmpty()) {
            int smallest = minHeap.poll();
            set.remove(smallest);
            return smallest;
        } else {
            int smallest = next;
            next++;
            return smallest;
        }
    }
    
    public void addBack(int num) {
        if (num < next && !set.contains(num)) {
            minHeap.offer(num);
            set.add(num);
        }
    }
}

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet obj = new SmallestInfiniteSet();
 * int param_1 = obj.popSmallest();
 * obj.addBack(num);
 */