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](https://codeforces.net/profile/vgtcross). Special thanks to him.↵
↵
If you have questions or comments, please leave them below.
↵
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↵
-----------------------------------↵
↵
↵
↵
~~~~~↵
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](https://codeforces.net/profile/vgtcross). Special thanks to him.↵
↵
If you have questions or comments, please leave them below.
