__↵
↵
↵
Mex problems
↵
Mex refers to the minimum non-negative integer that is not present in an array of
↵
1. Quick Mex for Small Array
-----------------------------------↵
↵
-----------------------------------↵
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
↵
↵
~~~~~↵
int mex(vector<int>& numberArray) {↵
set<int> sett;↵
sett.insert(numberArray[i]);↵
for(i
if(!sett.count(i)) return i;↵
return -1;↵
}↵
~~~~~↵
↵
↵
↵
↵
-------------------↵
↵
The second approach involves sorting the array and then looping through the sorted array.
↵
↵
~~~~~↵
sort
int mex =
for(int e : numberArray) {↵
if (e == mex) {↵
mex++;↵
}↵
}↵
~~~~~↵
↵
↵
↵
3.
--------------------------
↵
The third approach is a
↵
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
↵
~~~~~↵
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
↵
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](https://ibell.hashnode.dev/)!
↵
If you have questions or comments, please leave them below.