Let's say we have given array of $n$ elements, now we want to create data structure that will allow us to get the MEX of its elements, MEX meaning the smallest positive integer that is not present in the set. More info from wikipedia. The data structure should also support insert and remove elements from itself.

In other words, we have given multiset with $n$ elements, we want to find MEX of itself, but we should support removing and adding elements.

What I was thinking was that we should first process the elements on some way, and then when adding new element in the set we should check if it is equal to the MEX, but there are many cases to worry about, so I couldn't come to complete solution.

The data structure should support both the queries/updates in $O(logN)$ or similar time complexity classes.

  • $\begingroup$ Are all elements known beforehand? If so, you can use index compression and fenwick tree to maintain the elements present in your multiset. To query for MEX, you can binary search on the prefix sum in $\mathcal{O}(\log^2{n})$ time. $\endgroup$ – neutron-byte Feb 24 '18 at 13:28
  • $\begingroup$ The initial elements are known, however it may be possible that new elements will be inserted that have nott been there before $\endgroup$ – someone12321 Feb 24 '18 at 13:29
  • $\begingroup$ OK, the method I described in the first comment still works without index compression, but requires $\mathcal{O}(\log^2{C})$ time per query and $\mathcal{O}(C)$ space where $C$ denotes the largest element. Is that good enough? $\endgroup$ – neutron-byte Feb 24 '18 at 13:33
  • $\begingroup$ Neat question. What's the context where you encountered this problem? Have you tried augmenting a balanced binary search tree? $\endgroup$ – D.W. Feb 24 '18 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.