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.

This blog entry is meant to be more of an intro to this topic. For a full breakdown, you can also refer to: https://cp-algorithms.com/sequences/mex.html

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.

Examples of Mex Calculation

Quick Mex for Small Array Values

Array: [3, 1, 4, 0, 2] Mex: 5 Explanation: All integers from 0 to 4 are present in the array, so the Mex is 5. Sorting Approach:

Array: [2, 2, 1, 3, 0] Mex: 4 Explanation: After sorting, the array becomes [0, 1, 2, 2, 3], and the Mex is 4. Efficient O(n) Approach:

Array: [1, 1, 2, 0] Mex: 3 Explanation: Using the efficient O(n) method, the Mex is calculated as 3. Applications of Mex Calculation Game Theory: In combinatorial game theory, Mex is used to determine the Grundy number of a game position. It helps in solving impartial games using the Sprague-Grundy theorem. For more info please see:

Memory Management: In computer systems, Mex can be used to find the smallest available memory block, optimizing memory allocation.

Graph Coloring: Mex can be applied in graph algorithms to find the smallest unused color when coloring vertices.

Closing Note

I appreciate this community's feedback, which helped me correct the content. Mistakes are a part of growth, and I'm committed to growing and improving alongside all of you. I look forward to sharing more insights in the future, and I will consider all feedback as I build into a great writer.