#2336

Smallest Number in Infinite Set

pupil · 560 · lc medium +28 · 70.6% accepted · 1,845 likes · top 79%

Description

You have an infinite set that initially contains all positive integers [1, 2, 3, 4, 5, ...].

Implement the SmallestInfiniteSet class:

- SmallestInfiniteSet() Initializes the object with all positive integers present.

- int popSmallest() Removes and returns the smallest integer currently in the set.

- void addBack(int num) Adds num back into the set if it is not already there.

Example 1:

Input

["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]

[[], [2], [], [], [], [1], [], [], []]

Output

[null, null, 1, 2, 3, null, 1, 4, 5]

Example 2:

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.

Code

class SmallestInfiniteSet:

    def __init__(self):
        

    def popSmallest(self) -> int:
        

    def addBack(self, num: int) -> None:
        


# Your SmallestInfiniteSet object will be instantiated and called as such:
# obj = SmallestInfiniteSet()
# param_1 = obj.popSmallest()
# obj.addBack(num)

class SmallestInfiniteSet:

    def __init__(self):
        

    def popSmallest(self) -> int:
        

    def addBack(self, num: int) -> None:
        


# Your SmallestInfiniteSet object will be instantiated and called as such:
# obj = SmallestInfiniteSet()
# param_1 = obj.popSmallest()
# obj.addBack(num)