Mex problems refer to the minimum non-negative integer that is not present in an array of positive integers. Solving Mex problems requires finding an efficient algorithm to determine the missing number. It's not uncommon for this topic to come up in contests, usually as one part of a bigger solution to a problem. In this blog post, we’ll explore three different approaches to solving Mex problems.

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. We can create a set and insert each element from the array into the set. Then we loop through the numbers from 0 to 1 million and return the first number that is not present in the set.

int mex(vector<int>& numberArray) {
  set<int> sett;

  fo(i, numberArray.size()) 
    sett.insert(numberArray[i]);
  fo(i, 1000001)
    if(!sett.count(i)) return i;
  return -1;
}

Additionally, this approach can be optimized further with coordinate compression.

2. Sorting Approach

The second approach involves sorting the array and then looping through the sorted array. We start with mexas 1 and increment it whenever we come across a number that is equal to mex. After the loop, mex will be the answer. This approach takes O(N log N)time.

sortall(numberArray);
int mex = 1;
for(int e : numberArray) {
 if (e == mex) {
  mex++;
 }
}

3. More Sophisticated Approach

The third approach is a more sophisticated approach that involves removing elements greater than N from the array, sorting the array, and then analyzing the sequence. This approach takes O(N log N)time. The steps are as follows:

1. Go through the array and remove elements that are greater than N.

2. Sort the array.

3. Traverse the sequence and look at the first number that does not correspond to the position in the array.

For example, if we have an array [0, 3, 5, 7, 2, 4, 1, 10, 19] and N = 9, we would remove the numbers greater than 9, leaving us with [0, 3, 5, 7, 2, 4, 1].

Then, we would sort the array to get [0, 1, 2, 3, 4, 5, 7].

Finally, we would traverse the sorted array and look for the first number that does not correspond to its position. In this case, the first number that doesn’t match its position is 6, so the answer is 6.

Conclusion

-------------- There are multiple approaches to solving Mex problems, and each approach has its own advantages and limitations. When deciding which approach to use, consider the size of the array and the required time complexity.

If you have questions or comments, please leave them below. Stay tuned for a continuation on how to perform offline MEX queries.

Also, if you liked this article please consider subscribing to my newsletter!