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

# | User | Rating |
---|---|---|

1 | tourist | 3771 |

2 | jiangly | 3688 |

3 | Um_nik | 3539 |

4 | slime | 3498 |

5 | djq_cpp | 3486 |

6 | MiracleFaFa | 3466 |

7 | ksun48 | 3452 |

8 | Radewoosh | 3406 |

9 | greenheadstrange | 3393 |

10 | xtqqwq | 3382 |

# | User | Contrib. |
---|---|---|

1 | -is-this-fft- | 183 |

2 | awoo | 181 |

3 | YouKn0wWho | 177 |

4 | Um_nik | 175 |

5 | dario2994 | 172 |

6 | Monogon | 170 |

6 | adamant | 170 |

8 | maroonrk | 169 |

9 | antontrygubO_o | 165 |

10 | errorgorn | 164 |

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

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/16/2022 13:15:27 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by u1804011 (previous revision, new revision, compare).For c++, just use set. But it will only work for arr[i] <= 1000000.

If value is not matter, we can compress the array so that each element will have the value in

`[1..n]`

UwUhow bro can u tell me this ?

I don't think there is any better way than

`O(n)`

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

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

sorting 0 1 2 3 4 5 7

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

So if we are finding Mexico for subtree just remove the values less than mex of the node for its parent,, yeah I was wondering a approach didn't understand and that's why I neglected this , sometimes easy is smart

Thankyou

boss this only works for non rep elements

Consider your values are stored in

`vector<int> a`

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

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

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

:)I am also using this one.

Great description ;)

Cool and Thanks!

:)Very good explanation

Thanks!

:)thanks for ur contribution

it's my pleasure!

:)Awesome explanation...

Hii

hlo

Can you provide your code??

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

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

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

:)Seems like there's a

`O(n)`

way to do this if you don't have to change the array elements.First create a set of the array (in

`O(n)`

time). Then check all numbers from 0 to n, if it is not present in that set, return the current number as MEX. If all the numbers from 0 to n are present, return n + 1 as MEX.O(n) approach: Find sum of all the numbers and subtract from n(n+1)/2 this is will find the minimum missing number. If duplicates exist then remove them first, use set for this. (it has to be a permutation with one missing number)