Mex Puzzle

Intuition

The intuition is going to be very straightforward; for every query, we will first store the frequencies of the numbers that are present in the array, Then we will use these frequencies as numbers and store them in another hashmap so that it becomes easy to check whether there exists this frequency or not. Then we will loop through 1 to INT_MAX and check whether that particular is present or not. 

Things will become more clear from the following code.

Code

#include <bits/stdc++.h>
using namespace std;

int mex(vector<int> arr, int l, int r)
{
    /*This is done because input is given 1-indexed */
    l--;
    r--;

    /*To store the frequencies */
    unordered_map<int, int> freqStore;

    unordered_map<int, int> freqValue;
    for (int i = l; i <= r; i++)
    {
        freqStore[arr[i]]++;
    }

    /*Treating frequencies as numbers */
    for (auto it = freqStore.begin(); it != freqStore.end(); it++)
    {
        freqValue[it->second]++;
    }

    /*For Mex */
    for (int i = 1; i < INT_MAX; i++)
    {
        if (freqValue.find(i) == freqValue.end())
            return i;
    }
    return 0;

}

int main()
{
    int n;
    cin >> n;
    int q;
    cin >> q;
    vector<int> arr(n, 0);

    /*Taking input*/
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        arr[i] = x;
    }

    for (int i = 0; i < q; i++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int l, r;
            cin >> l >> r;
            cout << mex(arr, l, r) << endl;
        }
        if (type == 2)
        {
            int p, x;
            cin >> p >> x;
            arr[p] = x;
        }
    }

    return 0;
}

Input

10 4
1 2 3 1 1 2 2 2 9 9
1 1 1
1 2 8
2 7 1
1 2 8

Output

2
3
2

Complexities

Time Complexity

O(Q * N * INT_MAX) , where n and q are in the inputs

Reason: As we are looping over 'Q’ queries, it will cost us O(Q) time, and inside each query, we are using a loop to store the frequencies of the numbers that are present in the array that will cost us O(N) time. Also, for checking the Mex we are looping from 1 to INT_MAX. In the worst case, we will be traversing till INT_MAX. Thus, the overall time complexity to O(Q) * O(N) * O(INT_MAX) ~ O(Q * N * INT_MAX).

Space Complexity

O(N), where n is the input

Reason: We are using two hashmaps to store the frequency of the numbers present in the array, which in the worst case will take O(N) space. 

Check out this problem - Longest Subarray With Sum K 

FAQs

1. What is the Mex of a multiset?
   Mex of any given multiset of numbers is the smallest integer(non-negative) that is not present in the set. It could be anything from 1 to INT_MAX. For example Mex of set {1,3,4} is 2.
    
2. What is HashMap, and how does it work?
   A HashMap is a map used to store mappings of key-value pairs. HashMap in Java works on hashing principles. It is a data structure that allows us to store an object and retrieve it in constant time O(1), provided we know the key. 
    
3. What is a hash function in data structure?
   A hash function is a function that takes a set of arbitrary-sized inputs and fits them into a table or other data structure with fixed-size elements.
    
4. What is the time taken to find out Mex?
   We know that Mex is the smallest integer(non-negative) that is not present in the set. Thus to find it out, we have to traverse for every possible case, i.e., from 1 to INT_MAX. Thus in the worst case, it costs us O(INT_MAX) time.
    
5. Is there anything more in Coding Ninjas Studio that deals with Data Structures and Algorithms?
   Yes, Coding Ninjas Studio is a platform that offers both coding exercises and frequently asked interview questions. The more we practice, the greater our chances of landing a job at our ideal organization.

Key Takeaways

We saw how we solved the problem 'Mex Puzzle' using Hashmaps. Some other problems that involve Hashmaps and Mex are LRU cache, Find MEX of every subtree in the given Tree. Now don't waste any more time and head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, interview experiences, and many more. 
Till then, Happy Coding!