Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 25

Description

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.

Example 1:

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.

Solution

class SmallestInfiniteSet {
  set<int> back;
  int smallest;
public:
  SmallestInfiniteSet() {
    smallest = 1;
  }
  
  int popSmallest() {
    int result;
    if(back.size()) {
      result = *back.begin();
      back.erase(back.begin());
    } else {
      result = smallest;
      smallest += 1;
    }
    return result;
  }
  
  void addBack(int num) {
    if(num < smallest) {
      back.insert(num);
    }
  }
};

// Accepted
// 135/135 cases passed (92 ms)
// Your runtime beats 67.35 % of cpp submissions
// Your memory usage beats 84.48 % of cpp submissions (35.5 MB)