MEX (Minimum Excluded) in Competitive Programming
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.
How to Find MEX of an array (Without Updates) ?
Given an array arr of size N, the task is to determine the MEX of the array.
Approach:
The idea is to use a map to store frequency of each element of an array. Then, iterate through non-negative integers from 0 to N, and return the first integer with a frequency of 0 in the map. This integer represents the smallest non-negative integer not present in the array, which is the MEX.
Below is the implementation of above approach
C++
#include <bits/stdc++.h> using namespace std; // Function to find the MEX of the array int mex(vector< int >& arr, int N) { // Create a map to store the frequency of each element map< int , int > mp; for ( int i = 0; i < N; i++) { mp[arr[i]]++; } // Initialize MEX to 0 int mex = 0; // Iterate through non-negative integers from 0 to N for ( int i = 0; i <= N; i++) { // Find the first integer with a frequency of 0 in the map if (mp[i] == 0) { mex = i; break ; } } // Return MEX as the answer return mex; } int main() { // Example array vector< int > arr = { 1, 0, 2, 4 }; int N = arr.size(); // Call the mex function and print the result cout << "MEX of the array: " << mex(arr, N) << endl; return 0; } |
Java
import java.util.HashMap; public class MinimumExcludedValue { // Function to find the MEX of the array static int mex( int [] arr, int N) { // Create a map to store the frequency of each element HashMap<Integer, Integer> mp = new HashMap<>(); for ( int i = 0 ; i < N; i++) { mp.put(arr[i], mp.getOrDefault(arr[i], 0 ) + 1 ); } // Initialize MEX to 0 int mex = 0 ; // Iterate through non-negative integers from 0 to N for ( int i = 0 ; i <= N; i++) { // Find the first integer with a frequency of 0 in the map if (!mp.containsKey(i)) { mex = i; break ; } } // Return MEX as the answer return mex; } public static void main(String[] args) { // Example array int [] arr = { 1 , 0 , 2 , 4 }; int N = arr.length; // Call the mex function and print the result System.out.println( "MEX of the array: " + mex(arr, N)); } } |
Python
# Function to find the MEX of the array def mex(arr): # Create a dictionary to store the frequency of each element freq_map = {} for num in arr: freq_map[num] = freq_map.get(num, 0 ) + 1 # Initialize MEX to 0 mex_val = 0 # Iterate through non-negative integers from 0 to N N = len (arr) for i in range (N + 1 ): # Find the first integer with a frequency of 0 in the dictionary if i not in freq_map: mex_val = i break # Return MEX as the answer return mex_val # Main function if __name__ = = "__main__" : # Example array arr = [ 1 , 0 , 2 , 4 ] # Call the mex function and print the result print ( "MEX of the array:" , mex(arr)) |
C#
using System; using System.Collections.Generic; using System.Linq; class MexAlgorithm { static int Mex( int [] arr, int N) { Dictionary< int , int > freqMap = new Dictionary< int , int >(); // Store the frequency of each element in the array for ( int i = 0; i < N; i++) { if (freqMap.ContainsKey(arr[i])) { freqMap[arr[i]]++; } else { freqMap[arr[i]] = 1; } } int mex = 0; // Iterate through non-negative integers from 0 to N for ( int i = 0; i <= N; i++) { // Find the first integer with a frequency of 0 in the dictionary if (!freqMap.ContainsKey(i) || freqMap[i] == 0) { mex = i; break ; } } return mex; } static void Main() { // Example array int [] arr = { 1, 0, 2, 4 }; int N = arr.Length; // Call the Mex function and print the result Console.WriteLine( "MEX of the array: " + Mex(arr, N)); } } |
Javascript
// Function to find the MEX of the array function mex(arr, N) { // Create a map to store the frequency of each element const mp = new Map(); for (let i = 0; i < N; i++) { if (mp.has(arr[i])) { mp.set(arr[i], mp.get(arr[i]) + 1); } else { mp.set(arr[i], 1); } } // Initialize MEX to 0 let mex = 0; // Iterate through non-negative integers from 0 to N for (let i = 0; i <= N; i++) { // Find the first integer with a frequency of 0 in the map if (!mp.has(i) || mp.get(i) === 0) { mex = i; break ; } } // Return MEX as the answer return mex; } // Main function function main() { // Example array const arr = [1, 0, 2, 4]; const N = arr.length; // Call the mex function and print the result console.log( "MEX of the array:" , mex(arr, N)); } // Call the main function main(); |
MEX of the array: 3
Time Complexity: O(N*logN )
Auxiliary Space: O(N)
How to Find MEX of an array (With Updates) ?
Given an array arr of size N, and q queries. In each query you are given two numbers (idx, val), you have to update the element at index idx with value val. The task is to determine the MEX of the array after each query.
Approach:
The idea is to use a map to store frequency of each element of an array. Then insert all the numbers in the set from 0 to N which are not present in the array. For each query, update the array and maintain the map and set accordingly. The MEX for each query is determined by selecting the smallest element from the set and added to the result.
Step-by-step approach:
- Create a map to store the frequency of array elements and a set to store the elements(from 0 to N) which are not present in the array.
- For each query.
- Decrement the frequency of the element which is being replaced. If the frequency becomes 0, that element is added to set since it is not present in the array.
- Increment the frequency of the updated element. Remove the updated element from the set if the set contains it, since the updated element will be present in the set.
- The MEX for each query is determined by selecting the smallest element from the set and added to the result.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to calculate the MEX of an array after a series // of queries vector< int > mex(vector< int >& arr, int N, vector<vector< int > > queries, int q) { // Initialize a map to store element frequencies map< int , int > mp; // Initialize a set to store non-present elements set< int > st; // Populate the map for the initial array for ( int i = 0; i < N; i++) { mp[arr[i]]++; } // Add the elements to set which are not present in the // array. for ( int i = 0; i <= N; i++) { if (mp[i] == 0) st.insert(i); } // Initialize a vector to store MEX values after each // query vector< int > mex; // Process each query for ( int i = 0; i < q; i++) { int idx = queries[i][0]; int val = queries[i][1]; // Update the frequency of element which being // replaced. mp[arr[idx]]--; // If the frequency of element which is being // replaced becomes 0, add it to set. if (mp[arr[idx]] == 0) { st.insert(arr[idx]); } arr[idx] = val; mp[arr[idx]]++; // If the updated element is in the set, remove it if (st.find(arr[idx]) != st.end()) st.erase(arr[idx]); // Calculate the MEX and add it to the result vector int ans = *st.begin(); mex.push_back(ans); } return mex; } // Driver Code int main() { // Example array vector< int > arr = { 1, 0, 2, 4, 7 }; int N = arr.size(); // Example queries vector<vector< int > > queries = { { 1, 3 }, { 0, 0 }, { 4, 1 }, { 2, 10 } }; int q = queries.size(); // Call the 'mex' function to calculate MEX values after // each query vector< int > ans = mex(arr, N, queries, q); // Print the results for ( int i = 0; i < q; i++) { cout << "MEX of the array after query " << i + 1 << " : " << ans[i] << endl; } return 0; } |
Java
import java.util.*; public class Main { // Function to calculate the MEX of an array after a series // of queries static List<Integer> mex(List<Integer> arr, int N, List<List<Integer>> queries, int q) { // Initialize a map to store element frequencies Map<Integer, Integer> mp = new HashMap<>(); // Initialize a set to store non-present elements TreeSet<Integer> st = new TreeSet<>(); // Populate the map for the initial array for ( int i = 0 ; i < N; i++) { mp.put(arr.get(i), mp.getOrDefault(arr.get(i), 0 ) + 1 ); } // Add the elements to set which are not present in the array for ( int i = 0 ; i <= N; i++) { if (!mp.containsKey(i)) st.add(i); } // Initialize a list to store MEX values after each query List<Integer> mex = new ArrayList<>(); // Process each query for ( int i = 0 ; i < q; i++) { int idx = queries.get(i).get( 0 ); int val = queries.get(i).get( 1 ); // Update the frequency of element which is being replaced mp.put(arr.get(idx), mp.get(arr.get(idx)) - 1 ); // If the frequency of the element which is being replaced becomes 0, add it to set if (mp.get(arr.get(idx)) == 0 ) { st.add(arr.get(idx)); } arr.set(idx, val); mp.put(val, mp.getOrDefault(val, 0 ) + 1 ); // If the updated element is in the set, remove it if (st.contains(arr.get(idx))) st.remove(arr.get(idx)); // Calculate the MEX and add it to the result list int ans = st.first(); mex.add(ans); } return mex; } // Driver Code public static void main(String[] args) { // Example array List<Integer> arr = new ArrayList<>(Arrays.asList( 1 , 0 , 2 , 4 , 7 )); int N = arr.size(); // Example queries List<List<Integer>> queries = new ArrayList<>( Arrays.asList( Arrays.asList( 1 , 3 ), Arrays.asList( 0 , 0 ), Arrays.asList( 4 , 1 ), Arrays.asList( 2 , 10 ) ) ); int q = queries.size(); // Call the 'mex' function to calculate MEX values after each query List<Integer> ans = mex(arr, N, queries, q); // Print the results for ( int i = 0 ; i < q; i++) { System.out.println( "MEX of the array after query " + (i + 1 ) + " : " + ans.get(i)); } } } |
Python3
def mex(arr, N, queries, q): # Initialize a dictionary to store element frequencies mp = {} # Initialize a set to store non-present elements st = set () # Populate the dictionary for the initial array for num in arr: mp[num] = mp.get(num, 0 ) + 1 # Add the elements to set which are not present in the array. for i in range (N + 1 ): if i not in mp: st.add(i) mex = [] # Initialize a list to store MEX values after each query # Process each query for i in range (q): idx, val = queries[i] # Update the frequency of the element being replaced. mp[arr[idx]] - = 1 # If the frequency of the element being replaced becomes 0, add it to the set. if mp[arr[idx]] = = 0 : st.add(arr[idx]) arr[idx] = val # Update the frequency of the new element. mp[val] = mp.get(val, 0 ) + 1 # If the updated element is in the set, remove it. if arr[idx] in st: st.remove(arr[idx]) # Calculate the MEX and add it to the result list ans = min (st) mex.append(ans) return mex # Example array arr = [ 1 , 0 , 2 , 4 , 7 ] N = len (arr) # Example queries queries = [ [ 1 , 3 ], [ 0 , 0 ], [ 4 , 1 ], [ 2 , 10 ] ] q = len (queries) # Call the 'mex' function to calculate MEX values after each query ans = mex(arr, N, queries, q) # Print the results for i in range (q): print (f "MEX of the array after query {i + 1}: {ans[i]}" ) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Function to calculate the MEX of an array after a series // of queries static List< int > Mex(List< int > arr, int N, List<List< int >> queries, int q) { // Initialize a dictionary to store element frequencies Dictionary< int , int > mp = new Dictionary< int , int >(); // Initialize a HashSet to store non-present elements HashSet< int > st = new HashSet< int >(); // Populate the dictionary for the initial array foreach ( int num in arr) { if (mp.ContainsKey(num)) mp[num]++; else mp[num] = 1; } // Add the elements to set which are not present in the array. for ( int i = 0; i <= N; i++) { if (!mp.ContainsKey(i)) st.Add(i); } // Initialize a list to store MEX values after each query List< int > mex = new List< int >(); // Process each query foreach (List< int > query in queries) { int idx = query[0]; int val = query[1]; // Update the frequency of element which is being replaced. mp[arr[idx]]--; // If the frequency of element which is being replaced becomes 0, add it to set. if (mp[arr[idx]] == 0) st.Add(arr[idx]); arr[idx] = val; if (mp.ContainsKey(val)) mp[val]++; else mp[val] = 1; // If the updated element is in the set, remove it if (st.Contains(val)) st.Remove(val); // Calculate the MEX and add it to the result list int ans = st.Min(); mex.Add(ans); } return mex; } // Driver Code static void Main( string [] args) { // Example array List< int > arr = new List< int > { 1, 0, 2, 4, 7 }; int N = arr.Count; // Example queries List<List< int >> queries = new List<List< int >> { new List< int > { 1, 3 }, new List< int > { 0, 0 }, new List< int > { 4, 1 }, new List< int > { 2, 10 } }; int q = queries.Count; // Call the 'Mex' function to calculate MEX values after each query List< int > ans = Mex(arr, N, queries, q); // Print the results for ( int i = 0; i < q; i++) { Console.WriteLine($ "MEX of the array after query {i + 1} : {ans[i]}" ); } } } |
Javascript
function calculateMex(arr, N, queries, q) { // Initialize a dictionary to store element frequencies let mp = new Map(); // Initialize a Set to store non-present elements let st = new Set(); // Populate the dictionary for the initial array arr.forEach((num) => { mp.set(num, (mp.get(num) || 0) + 1); }); // Add the elements to set which are not present in the array for (let i = 0; i <= N; i++) { if (!mp.has(i)) { st.add(i); } } // Initialize a list to store MEX values after each query let mex = []; // Process each query for (let i = 0; i < q; i++) { let idx = queries[i][0]; let val = queries[i][1]; // Update the frequency of element which is being replaced mp.set(arr[idx], mp.get(arr[idx]) - 1); // If the frequency of element which is being replaced becomes 0, add it to set if (mp.get(arr[idx]) === 0) { st.add(arr[idx]); } arr[idx] = val; if (mp.has(val)) { mp.set(val, mp.get(val) + 1); } else { mp.set(val, 1); } // If the updated element is in the set, remove it if (st.has(val)) { st. delete (val); } // Calculate the MEX and add it to the result list let ans = Math.min(...Array.from(st)); mex.push(ans); } return mex; } // Example array let arr = [1, 0, 2, 4, 7]; let N = arr.length; // Example queries let queries = [ [1, 3], [0, 0], [4, 1], [2, 10] ]; let q = queries.length; // Call the 'calculateMex' function to calculate MEX values after each query let ans = calculateMex(arr, N, queries, q); // Print the results for (let i = 0; i < q; i++) { console.log(`MEX of the array after query ${i + 1} : ${ans[i]}`); } |
MEX of the array after query 1 : 0 MEX of the array after query 2 : 1 MEX of the array after query 3 : 5 MEX of the array after query 4 : 2
Time Complexity: O(N*logN )
Auxiliary Space: O(N)
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 ith query you add a element yi to the array. After each query you can perform the following operation any number of times: Choose an element arrj and set arrj to arrj +m or arrj -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: arrj +m or arrj -m on an element arrj, 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 freq0 , freq1 ,……, freqm-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 calculatey % m
to determine its remainder when divided bym
and then update its frequency.MEX Calculation: In each query after updating the frequency of remainder we will find the minimum of {freq0 , freq1 ,……, freqm-1 }. If frqj is remainder with minimum frequency the maximum MEX will be equal to: j*frqj + 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, arri = i. Let cnt be the number of indexes such that arri 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 arri 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.
Contact Us