[LeetCode] Smallest Number in Infinite Set

Problem: 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:

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 <= 1000
• At most 1000 calls will be made in total to popSmallest and addBack.

Apporach: We can solve this problem using priority queue as we need a data structure which stores the input integers in sorted order given we always have to return smallest number.

The only problem here is how to avoid duplicates as we can have multiple addBack calls for the same number and we don't want to add the same number multiple times. To avoid this situation I am using a HashSet to track the added numbers.

Rest of the solution is straight forward. You can understand it by just looking at the implementation.

Implementation in C#:

public class UniquePriorityQueue

{

    public UniquePriorityQueue()

    {

        this.pq = new PriorityQueue<int, int>();

        this.uniqueSet = new HashSet<int>();

    }

   

    public void Enqueue(int num)

    {

        if (!this.uniqueSet.Contains(num))

        {

            this.pq.Enqueue(num, num);

            this.uniqueSet.Add(num);

        }

    }

    public int Dequeue()

    {

        int num = this.pq.Dequeue();

        this.uniqueSet.Remove(num);

        return num;

    }

    public int Count { get => this.pq.Count; private set{}}

    private PriorityQueue<int, int> pq;

    private HashSet<int> uniqueSet;

}

public class SmallestInfiniteSet

{

    public SmallestInfiniteSet()

    {

        this.pq = new UniquePriorityQueue();

        this.minValue = 1;

        this.maxValue = 1000;

    }

   

    public int PopSmallest()

    {

        if (this.pq.Count > 0)

        {

            return this.pq.Dequeue();

        }

        return this.minValue++;

    }

   

    public void AddBack(int num)

    {

        if (num < this.minValue)

        {

            this.pq.Enqueue(num);

        }

    }

    private UniquePriorityQueue pq;

    private int minValue;

    private int maxValue;

}

Complexity: popSmallest: O(logn), addBack: O(logn)