Problem of The Day: Smallest Number in Infinite Set

Problem Statement

leetcode problem link

My Solution [Accepted]

public class SmallestInfiniteSet {
    private PriorityQueue<int, int> PriorityQueue { get; set;}
    private HashSet<int> hashSet { get; set; }
    private int Current { get; set;} = 1;
    private int _limit = 1000;

    public SmallestInfiniteSet() {
        PriorityQueue = new PriorityQueue<int, int>();
        hashSet = new HashSet<int>();
        for (int i = 0; i < _limit; i++) {
            PriorityQueue.Enqueue(i + 1, i + 1);
            hashSet.Add(i + 1);
        }
    }

    public int PopSmallest() {
        int current = PriorityQueue.Dequeue();
        if (hashSet.Contains(current)) {
            hashSet.Remove(current);
        }
        return current;
    }

    public void AddBack(int num) {
        if (hashSet.Contains(num))
            return;
        PriorityQueue.Enqueue(num, num);
        hashSet.Add(num);
    }
}

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

Editorial

Approach 1: Hashset + Heap

class SmallestInfiniteSet:
    def __init__(self):
        self.is_present: {int} = set()
        self.added_integers: [int] = []
        self.current_integer = 1

    def popSmallest(self) -> int:
        # If there are numbers in the min-heap,
        # top element is lowest among all the available numbers.
        if len(self.added_integers):
            answer = heapq.heappop(self.added_integers)
            self.is_present.remove(answer)
        # Otherwise, the smallest number of large positive set
        # denoted by 'current_integer' is the answer.
        else:
            answer = self.current_integer
            self.current_integer += 1
        return answer

    def addBack(self, num: int) -> None:
        if self.current_integer <= num or num in self.is_present:
            return
        # We push 'num' in the min-heap if it isn't already present.
        heapq.heappush(self.added_integers, num)
        self.is_present.add(num)

Approach 2: Sorted Set

from sortedcontainers import SortedSet

class SmallestInfiniteSet:
    def __init__(self):
        self.added_integers = SortedSet()
        self.current_integer = 1
    def popSmallest(self) -> int:
        # If there are numbers in the sorted-set,
        # top element is lowest among all the available numbers.
        if len(self.added_integers):
            answer = self.added_integers[0]
            self.added_integers.discard(answer)
        # Otherwise, the smallest number of large positive set
        # denoted by 'current_integer' is the answer.
        else:
            answer = self.current_integer
            self.current_integer += 1
        return answer
    def addBack(self, num: int) -> None:
        if self.current_integer <= num or num in self.added_integers:
            return
        # We push 'num' in the sorted-set if it isn't already present.
        self.added_integers.add(num)