isaacbell's blog

3 Approaches to Calculating the Mex of an Array
By isaacbell, history, 16 months ago, In English

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.

  • Vote: I like it
  • -10
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
16 months ago, # |
← Rev. 3   Vote: I like it +35 Vote: I do not like it

In this blog post, we’ll explore three different approaches to solving Mex problems.

This is very misleading. You didn't show any approaches to solving any problems related to Mex — you just listed three ways of calculating the Mex of an array.

Method 3 fails if the array contains duplicate elements: $$$[1, 2, 1, 0]$$$ becomes $$$[0, 1, 1, 2]$$$ when sorting; the first number not equaling its index is $$$1$$$, while Mex is $$$3$$$.

Also, it's funny that you mentioned three different ways of calculating Mex in $$$O(n\log n)$$$ and didn't realize that it can be done in $$$O(n)$$$:

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$$$.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Hey, apologies, this was my first blog entry and you're right, I made some mistakes. I will improve this entry. If you don't mind, I will incorporate your suggestion.

    And seriously, thank you for pointing it out.

    → Reply
»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

it's better not using macros in tutorial blogs

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Thanks! This is my first blog post. I will edit this and do better going forward

    → Reply
»
16 months ago, # |
  Vote: I like it +27 Vote: I do not like it

You can do it in-space and in linear time as well

int mex(vector<int> a){
	int n = a.size();
	for(int i = 0; i < n; i++){
		while(a[i] >= 0 && a[i] < n && a[a[i]] != a[i]){
			swap(a[i],a[a[i]]);
		}
	}
	for(int i = 0; i < n; i++){
		if(a[i] != i){
			return i;
		}
	}
	return n;
}
→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you don't mind can you please explain how does this work

    while(a[i] >= 0 && a[i] < n && a[a[i]] != a[i]){
			swap(a[i],a[a[i]]);
}
    → Reply