SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The SmallestInfiniteSet class manages a set of integers starting from 1 to 1000. The class allows two main operations: removing the smallest integer from the set and adding back an integer that was previously removed.

The popSmallest() function removes and returns the smallest number in the set. The addBack() function allows adding a number back into the set if it has been removed before.

Intuition

The intuition behind the SmallestInfiniteSet is to efficiently manage a collection of integers where the smallest number can always be accessed and removed quickly. By maintaining the numbers in a sorted set, it becomes easy to identify and remove the smallest element. Re-adding elements to the set ensures that they are placed in the correct order for future operations.

Approach

1. Initialization:
   • A set or equivalent structure is initialized with integers ranging from 1 to 1000.
2. popSmallest():
   • This method finds the smallest number in the set, removes it from the set, and returns it.
3. addBack():

   • This method takes a number as input and adds it back to the set only if it isn't already present.

   • In C++ and Java, a TreeSet or std::set is used to maintain the order and provide efficient insertion, deletion, and smallest element retrieval.

   • In Python, a standard set is used, and the smallest element is found using the min() function.

Complexity

Time Complexity:

• popSmallest():
  • C++/Java: O(log n) due to the nature of the balanced tree structure used (TreeSet or std::set).
  • Python: O(n) due to the need to iterate through the set to find the minimum.
• addBack():
  • C++/Java: O(log n) for insertion.
  • Python: O(1) for insertion in the set.

Space Complexity:

O(n) where n is the number of elements managed by the set, which is initially 1000.

Code

C++

class SmallestInfiniteSet {
private:
    std::set<int> set;
public:
    SmallestInfiniteSet() {
        for (int i = 1; i <= 1000; i++) {
            set.insert(i);
        }
    }

    int popSmallest() {
        if (set.empty()) return -1;

        int min = *set.begin();
        set.erase(set.begin());
        return min;
    }

    void addBack(int num) {
        set.insert(num);
    }
};

Python

class SmallestInfiniteSet:
    def __init__(self):
        self.set = set(range(1, 1001))

    def popSmallest(self) -> int:
        if not self.set:
            return None

        min_val = min(self.set)
        self.set.remove(min_val)
        return min_val

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

Java

class SmallestInfiniteSet {
    private TreeSet<Integer> set;

    public SmallestInfiniteSet() {
        set = new TreeSet<>();
        for (int i = 1; i <= 1000; i++) {
            set.add(i);
        }
    }

    public int popSmallest() {
        if (set.isEmpty()) return -1;

        int min = set.first();
        set.remove(min);
        return min;
    }

    public void addBack(int num) {
        set.add(num);
    }
}

JavaScript

class SmallestInfiniteSet {
  constructor() {
    this.set = new Set(Array.from({ length: 1001 }, (_, i) => i + 1));
  }
}
/**
 * @return {number}
 */
SmallestInfiniteSet.prototype.popSmallest = function() {
  if (this.set.size === 0) return null;

  let min = Infinity;

  for (const num of this.set) {
    if (num < min) {
      min = num;
    }
  }

  this.set.delete(min);
  return min;
};

SmallestInfiniteSet.prototype.addBack = function(num) {
     if (!this.set.has(num)) this.set.add(num)
};