Important Note

This is my first blog entry, and I want to acknowledge that some mistakes were initially made. I'm grateful for the community's feedback, which has allowed me to make corrections. I will note areas where I've made corrections below.

Special thanks to @vgtcross and @brownfox2k6 for their input on this article.

Intro

Mex, or the minimum excludant, is a concept that refers to the smallest non-negative integer not present in a given array of non-negative integers. Understanding Mex is essential in various fields such as computer science and mathematics, where it plays a crucial role in algorithm design and optimization. In this blog post, we'll delve into three different approaches to calculating Mex in an array, each with its unique characteristics and use cases.

1. Quick Mex for Small Array Values

When dealing with small array values, specifically when all values are less than 1 million, a set can be used to calculate Mex. This approach leverages the constant time lookups of a set, making it efficient for small values. While effective for small values, this method may become inefficient for values larger than 1 million, as the set's size can lead to increased memory consumption and slower performance.

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

Another way to calculate Mex is by sorting the array first and then looping through the sorted array. This approach takes O(N log N) time due to the sorting step. The sorting step takes O(N log N) time, which can become a bottleneck for very large arrays, making this method less suitable when performance is a critical concern.

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

3. Efficient O(n) Approach

For those looking for an efficient solution, an O(n) approach is available. Special thanks to @vgtcross for his contribution here. An O(n) approach is considered highly efficient as it allows the Mex to be calculated in linear time, making it suitable for large datasets.

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;
}

Applications of Mex Calculation

Game Theory In combinatorial game theory, Mex is used to determine the Grundy number of a game position, a concept that forms the basis of many combinatorial game-solving algorithms.

Memory Management In computer systems, Mex can be utilized to find the smallest available memory block, allowing for optimized memory allocation and reduced fragmentation.

Graph Coloring In graph algorithms, Mex can be applied to find the smallest unused color when coloring vertices, ensuring an efficient and conflict-free coloring process.

Closing Note

I appreciate this community's feedback, which has helped me correct and improve 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 will consider all feedback as I strive to become a great writer.