MEX (minimum excluded) of a sequence (with updates)

In this article, we have explored approaches to find the MEX (minimum excluded) of a sequence (with updates) efficiently with pre-computation.

Table of contents:

1. Problem statement: MEX of a sequence
2. Solution for MEX without updates
3. Solution for MEX with updates
4. Practice Problems for MEX

Problem statement: MEX of a sequence

Given an array A of size N. You have to find the minimum element that is not present in the array and is equal to or greater than 0.

There is an alternative problem statement where we can update elements in the array and have queries to find the MEX of the array. It support two operations:

• Update(X, i): Update element at index i to X
• MEX Query: Find the MEX of the array

The version with online updates is the challenging problem.

Solution for MEX without updates

If there are no update queries, then the problem can be solved in O(N) time. The answer will be same for all queries as the array does not change.

The steps to solve this problem efficiently are:

• Move all elements of the array into a HashMap or HashSet
• For each number from 0 to N-1:
  • Check if the current number M is in the HashSet
  • If it is not present, it is the answer/ MEX of the array.

This approach takes O(N) time as we traverse through the array once.

Sample implementation of the above approach in Python:

def mex(array):
    items = set(array)
    for i in range(len(array)):
        if i not in items:
            return i
    return len(array)

To learn more about efficient solutions for this problem statement, go through this article: Smallest Missing Positive Integer

Solution for MEX with updates

The above approach is fast but works well only if your array does npt change during program execution that is it does not support update queries. If we use the above approach for the version supporting updates, then the time complexity will be:

• Update: O(1)
• MEX Query: O(N)

As the number of queries increase, this is not an efficient version.

The efficient approach will involve a pre-computation of O(N logN) time and with this, the time complexity of the operations will be:

• Update: O(logN)
• MEX Query: O(1)

The efficient approach for MEX problem with update queries are as follows:

Precomputation:

• Create a frequency map with Hash Map or an Array.
• If element is outside the range 0 to N+1, remove the element.
• If element is within the range, add it to the set and update the frequency.

Depending on the data structure being used, Pre-computation step will take O(N) time. For a set implementation, this takes O(N logN) time.

For update operation:

• If the element to be replaced in within the range of 0 to N+1, then the frequency is reduced by 1. If the frequency becomes 0, then the element is removed from the set.
• Add the new element in the set and update the frequency.

This takes O(logN) time for the set.

For MEX query:

• The output MEX is the first element of the set.

Depending on the set implementation, this can be done in O(1) time.

The implementation is as follows:

ll n;
cin >> n;
vl a(n);
ain(a, n);
bool sorted = 1;
set<ll> mex;
loop(i, n + 1)	mex.insert(i);
map<ll, ll> f;
loop(i, n)	++f[a[i]];
loop(i, n)
{
    if (mex.find(a[i]) != mex.end())
        mex.erase(a[i]);
}
ll currmex = *(mex.begin()), iter = 0;
vl ans;
loop(i, n - 1)
{
    if (a[i] > a[i + 1])
    {
        sorted = 0;
        break;
    }
}
// cout << "Sorted : " << sorted << END;
while (iter < 2 * n && sorted == false)
{
    // cout << currmex << END;
    if (currmex == n)
    {
        loop(i, n)
        {
            if (a[i] != i)
            {
                ans.pb(i);
                --f[a[i]];
                if (f[a[i]] == 0)
                    mex.insert(a[i]);
                a[i] = currmex;
                ++f[currmex];
                mex.erase(currmex);
                break;
            }
        }
    }
    else
    {
        ans.pb(currmex);
        --f[a[currmex]];
        if (f[a[currmex]] == 0)
            mex.insert(a[currmex]);
        a[currmex] = currmex;
        ++f[currmex];
        mex.erase(currmex);
    }
    currmex = *(mex.begin());
    bool ok = 1;
    loop(i, n - 1)
    {
        if (a[i] > a[i + 1])
        {
            ok = 0;
            break;
        }
    }
    sorted = ok;
    ++iter;
}
// cout << "Sorted : " << sorted << END;
cout << ll(ans.size()) << END;
go(ans, itr)	cout << *itr + 1 << " ";
cout << END;

Practice Problems for MEX

Following are the practice problems that require the knowledge of finding MEX of an array with update queries:

• "Replace by MEX" problem

This problem states that one operation is permitted where one can replace the i-th element with the MEX of the array. One needs to find a sequence of such operations to make the array non-decreasing order.

• "MEX and Increments" problem

This problem states that one operation is permitted where one can increment the i-th element by 1.

One needs to find the minimum number of such operations to make the MEX of the array equal to a given number j. You need to do this for all possible values of j that is from 0 to N.

With this article at OpenGenus, you must have a strong hold on finding the MEX of an array.