1.
Introduction
2.
Understanding the Problem
2.1.
Example
3.
Intuition
3.1.
Code
3.1.1.
Input
3.1.2.
Output
3.2.
Complexities
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Mex Puzzle

Saksham Gupta
0 upvote

## Introduction

Often in O.A(Online Assessments), we see questions on Mex being asked. Therefore it's important to master such a topic. Mex of any given multiset of numbers is the smallest integer(nonnegative) that is not present in the set. Now for strengthening your concepts around Mex, we are here with an interesting problem, i.e., Mex Puzzle.

## Understanding the Problem

We have been given an array 'ARR' of length 'N,' and there are 'Q' queries that we have to answer. Queries are of two kinds.

• In the first one, you will be given two integers, ' L' and 'R.' Our task is to find the Mex of the subarray formed by the occurrences of the numbers present in the subarray of 'ARR' from the Lth element to the Rth element(Inclusive).
• In the second one, you will be given two integers, i.e., p and x. Our task is to simply change the element at pth index to x.

Let's understand this by the following example.

### Example

Input

ARR =  [1, 2, 3, 1, 1, 2, 2, 2, 9, 9]

Queries
1 1 1
1 2 8
2 7 1
1 2 8

Output

2
3
3

Explanation

• In the first query, values of ‘L’ and ‘R’ are 1 and 1, respectively; thus, the subarray formed is [1]. Now 1 has 1 frequency, so the frequency array is [1]. In this array, the smallest number that is not present in the array is 2. Thus we will print 2.
• In the second query, values of ‘L’ and ‘R’ are 2 and 8, respectively. Thus the subarray formed is [2, 3, 1, 1, 2, 2, 2, 9]. Now frequency array will be [1, 1, 2, 4]. In this array, the smallest number that is not present in the array is 3. Thus we will print 3.
• The third query is of the second type. Thus, we will simply change ARR[7]=1.
• In the third query, values of ‘L’ and ‘R’ are 2 and 8, respectively; thus, the subarray formed is [2, 3, 1, 1, 1, 2, 2, 9]. Now frequency array will be [1, 1, 3, 3]. In this array, the smallest number that is not present in the array is 2. Thus we will print 2.

Check out Euclid GCD Algorithm

## 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!

Live masterclass