How to solve MEX related problems in Competitive Programming ?

MEX Related tasks usually involves finding MEX of the array while updating its elements. Some of the common characteristics of MEX related tasks include:

• Array Updates – In general we are generally given queries in which we have either add, remove or update the values of array and the task involves finding the MEX after each such query.
• Data Structures- To optimally compute MEX after each query, set and maps are generally used because both provide fast lookup time for the elements (log n), also they keep elements sorted making it easier to find the minimum non-present element (MEX).

Let us consider few problems involving MEX:

Problem 1: Given an empty array arr[] and a integer m. You are given q queries. In i_th query you add a element y_i to the array. After each query you can perform the following operation any number of times: Choose an element arr_j and set arr_j to arr_j +m or arr_j -m. The task is maximize the value of MEX of array arr after each query.

The problem can be solved in following way:

Observation: We need to firstly observe that after applying the operation: arr_j +m or arr_j -m on an element arr_j, its modulo with m still remains the same after the operation.

Keep the track of Frequency: We keep track of frequency of remainders when divided by m, i.e., for each number [0,m-1] keep track of its frequency with each query. Let freq_{0 ,} freq₁ ,……, freq_m-1 be the frequency of remainders 0, 1, ….. m-1.

Query Updates: During each query, we update the frequency of the remainder, by keeping the set sorted based on frequency and remainder. For example, if the query adds an element y, we calculate y % m to determine its remainder when divided by m and then update its frequency.

MEX Calculation: In each query after updating the frequency of remainder we will find the minimum of {freq_{0 ,} freq₁ ,……, freq_m-1 }. If frq_j is remainder with minimum frequency the maximum MEX will be equal to: j*frq_j + j.

For example:- Suppose m=5 and frequency of remainders 0, 1, 2, 3, 4 are 3, 4, 4, 2 ,5 respectively. The minimum frequency is of remainder 3 with frequency 2. Since frequency of remainder 3 is 2, elements 3 and 8 will be present in the array by performing the operations. So the MEX will be 13 (2*10+3) in this case.

Problem 2: Given an array of n integers each integer lies in range [0,N]. The task is to make the array exactly {0, 1, 2,… , N-1} in almost 2*n operations. In one operation you can pick any element of the array and replace it with MEX of the array.

The problem can be solved in following way:

Observation: MEX of the array after each operation will lie between [0,N] and in the final array for each index i, arr_i = i. Let cnt be the number of indexes such that arr_i is not equal to i. Thus the cnt represents number of indexes for which we have to change the value of that index to its correct value.

Perform the Operations: In each operation we will firstly find the MEX of the array. Now we have 2 cases:
Case 1: When Mex of the array is between [0,N-1]: In this case we will simply put the MEX of the array in its correct index, i.e., if min_exc represents the MEX of the array then we will put min_exc in the index min_exc, this will decrease the value of cnt by 1.
Case 2: When Mex of the array is N: In this case, we will put the MEX of the array in any of the index for which arr_i is not equal to i. The value of cnt will remain the same.

Correctness: The above approach will convert array arr to {0,1,2, …. , N-1} in almost 2*N operations. The maximum value of cnt can be N, and the above approach decreases the value of cnt will by 1 in almost 2 operations because each time we encounter Case 2(MEX of the array is N), next time we perform the operation, we will get Case 1(MEX of the array is not N) since N was inserted in the array in last operation so MEX will not be N. Thus, we will Case 1 in which value of cnt will be decreased by 1. Hence, it takes almost 2*N operations to make the value of cnt 0.

MEX of a sequence or an array is the smallest non-negative integer that is not present in the sequence.

Example:

• If we have a sequence S[] = {1,2,0,4,5} then MEX (S) = 3.
• If we have a sequence S[] ={2,0,3,10} then MEX (S) = 1.
• If we have a sequence S[] ={1,2,3,4,5} then MEX (S) = 0.

Note: The MEX of an array of size N cannot be greater than N since the MEX of an array is the smallest non-negative integer not present in the array and array having size N can only cover integers from 0 to N-1. Therefore, the MEX of an array with N elements cannot be greater than N itself.