u1804011's blog

By u1804011, history, 6 weeks ago, In English

How can we efficeiently find MEX(minimum excluded) of an array?

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by u1804011 (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For c++, just use set. But it will only work for arr[i] <= 1000000.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If value is not matter, we can compress the array so that each element will have the value in [1..n] UwU

»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

I don't think there is any better way than O(n).

»
6 weeks ago, # |
Rev. 3   Vote: I like it +17 Vote: I do not like it
  1. go through the array and remove elements from it that are greater than N
  2. we use sorting for O (N) + unique O(N)
  3. we go through the sequence in the line and look at the first one that does not correspond to the number in the array

Example: n = 9, 0 3 5 7 2 4 1 10 19

  1. delete (>= n) 0 3 5 7 2 4 1

  2. sorting 0 1 2 3 4 5 7

  3. analysis of 0-index

0 in 0 position, 1 in 1 position ... 5 in 5 position, 7 in 6 position

then the answer is 6

//google translate

»
6 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Consider your values are stored in vector<int> a.

$$$O(N*lg(N))$$$

sort(a.begin(), a.end());
int mex = 1;
for (auto& e:a) {
	if (e == mex) {
		mex++;
	}
}

Although, if range for $$$A[i]$$$ are small enough, you can then sort in $$$O(N)$$$.

»
6 weeks ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

I saw all the other comments almost cover the approaches, although I'd like to share one of the approaches I use most frequently. The approach takes O(NlogN) precomputation, but each MEX query takes O(1) time and updates the MEX of an array in O(logN) for every point update in the array.
In C++ :-
Precomputation:
- Create a set and a frequency map(or array).
- Fill the set with all numbers from 0 to n+1.
- Now, traverse in the array, if the element is within [0, n+1] remove it from the set, and keep updating the frequency map(or array). It takes at worst O(NlogN) time.
- Now, for any state, the set.begin() will give the MEX of the current array.
For updates:
- If the element to be replaced, is within [0, n+1] then update its frequency in the frequency map(or array) and if after updating, the frequency of that element becomes zero, insert it into our set. It takes O(logN) time.
- Now if the element which is placed in that position is within [0, n+1] then update its frequency in the frequency map(or array) and remove it from our set(if its present). It takes O(logN) time.
- And yet again, after any update, set.begin() will give us the current MEX in O(1).

A sample code where I used this technique to find MEX in queries : 86004255 :)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm assuming that the elements are in the range [0, n] inclusive where n is the length of the array.

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

bool b[400005];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        b[x] = true;
    }
    for (int i = 0; i <= n; i++) {
        if (!b[i]) {cout << i; return 0;}
    }
}

I just use a bool array to keep track of the elements I've encountered and I output the smallest one I haven't.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually the range of the elements won't matter, only the elements in the range [0, n+1] will affect the MEX. :)