DEV Community

SalahElhossiny
SalahElhossiny

Posted on

Smallest Number in Infinite Set

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.

class SmallestInfiniteSet:
    import heapq
    def __init__(self):
        self.summary = list(range(1, 1001))
        heapq.heapify(self.summary)
        self.deleted = set()
    def popSmallest(self) -> int:
        A = heapq.heappop(self.summary)
        self.deleted.add(A)
        return A
    def addBack(self, num: int) -> None:
        if num in self.deleted:
            self.deleted.remove(num)
            heapq.heappush(self.summary, num)

Enter fullscreen mode Exit fullscreen mode

Top comments (0)