Important Note: This is my first blog entry, and some mistakes were pointed out in the comments. I appreciate the feedback and have made corrections accordingly.

Mex refers to the minimum non-negative integer that is not present in an array of non-negative integers. Calculating Mex is a common task in various algorithmic problems. In this blog post, we'll explore three different approaches to calculating Mex in an array.

1. Quick Mex for Small Array Values

The first approach is to use a set when the values in the array are small, specifically when all values are less than 1 million. This approach takes advantage of the set's constant time lookups.

int mex(vector<int>& numberArray) {
  set<int> sett;
  for(int i = 0; i < numberArray.size(); i++) 
    sett.insert(numberArray[i]);
  for(int i = 0; i < 1000001; i++)
    if(!sett.count(i)) return i;
  return -1;
}

2. Sorting Approach

The second approach involves sorting the array and then looping through the sorted array. This approach takes O(N log N) time.

sort(numberArray.begin(), numberArray.end());
int mex = 0;
for(int e : numberArray) {
 if (e == mex) {
  mex++;
 }
}

3. Efficient O(n) Approach

The third approach is an efficient O(n) method.

int mex(vector<int> &a) {
    vector<bool> f(a.size() + 1, 0);
    for (int i : a) if (i <= (int) a.size()) f[i] = 1;
    int mex = 0;
    while (f[mex]) ++mex;
    return mex;
}

This works because the Mex of n integers cannot exceed n.

Conclusion

There are multiple approaches to calculating Mex, and each approach has its own advantages and limitations. The efficient O(n) approach is particularly noteworthy, and it was supplied by @VGTCross. Special thanks to him.

If you have questions or comments, please leave them below.