How to Find MEX of an array (With Updates) ?

How to Find MEX of an array (Without Updates) ?

How to solve MEX related problems in Competitive Programming ?

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]}`);
}

Output

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)

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.

Tags:

#MEX (Minimal Excluded) #Competitive Programming #DSA