3
$\begingroup$

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 (Minimum EXcluded) 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 a multiset with $n$ elements, we want to find its MEX, 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(\log N)$ or similar time-complexity classes.

$\endgroup$
4
  • $\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$ Feb 24, 2018 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$ Feb 24, 2018 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$ Feb 24, 2018 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, 2018 at 16:33

1 Answer 1

3
$\begingroup$

Method 1
You can also use a bit trie — this is a trie made of bits of your numbers, thus it is represented as a binary tree (since there are only two types of bits — 0 and 1), and its depth is $\mathcal{O}{(log(n))}$.

When you add a number, you mark the vertex that representing this particular number as a full binary tree, and then you recursively go over its parents marking them as full binary trees if their left and right children are both full binary trees as well.

When you remove a number, you unset the "full binary tree" mark and do so for all its parents.

When you want to get MEX, you should do the DFS towards $x$, avoiding visiting subtrees which are marked as full (because there are no free values in such subtrees) and attempt to visit a left subtree first if you are allowed to by the x restriction.

class MEX {
  struct MEXNode {
    MEXNode *children[2];
    bool is_full = false;
    int cnt = 0;
  
  public:
    MEXNode() {
      children[0] = nullptr;
      children[1] = nullptr;
    }
  };
private:
  
  inline MEXNode *nonnull(MEXNode *& n) {
    if (!n) n = new MEXNode();
    return n;
  }
  
  void insert(int val, int level, MEXNode *n) {
    if (level == -1) {
      n->cnt++;
      n->is_full = true;
      return;
    }
    
    int cur_bit = (val & (1 << level)) >> level;
    insert(val, level - 1, nonnull(n->children[cur_bit]));
    
    n->is_full = nonnull(n->children[0])->is_full && nonnull(n->children[1])->is_full;
    n->cnt = nonnull(n->children[0])->cnt + nonnull(n->children[1])->cnt;
  }
  
  // Remove an integer from the set
  void remove(int val, int level, MEXNode *n) {
    if (level == -1) {
      n->cnt--;
      n->is_full = n->cnt > 0;
      return;
    }
    
    int cur_bit = (val & (1 << level)) >> level;
    remove(val, level - 1, nonnull(n->children[cur_bit]));
    
    n->is_full = nonnull(n->children[0])->is_full && nonnull(n->children[1])->is_full;
    n->cnt = nonnull(n->children[0])->cnt + nonnull(n->children[1])->cnt;
  }
  
  // Find the minimum element >=x that isn't present in the set
  int get(int val, int level, MEXNode *n) {
    if (n->is_full) {
      return -1;
    } else if (n->cnt == 0) {
      return val;
    }
    
    int cur_bit = (val & (1 << level)) >> level;
    int ans = get(val, level - 1, nonnull(n->children[cur_bit]));
    if (cur_bit == 0 && ans == -1) {
      ans = get((val >> level << level) | (1 << level), level - 1, nonnull(n->children[1]));
    }
    
    return ans;
  }
  
  MEXNode root_node;
public:
  
  void insert(int x) {
    insert(x, 31, &root_node);
  }
  void remove(int x) {
    remove(x, 31, &root_node);
  }
  int get(int x) {
    return get(x, 31, &root_node);
  }
};

Method 2
Create a set of intervals $S$. If the interval $[l, r]$ is present in $S$, that means that the elements $l, l + 1, l + 2, \dots , r$ are in $S$.

Adding an element $x$ is handled like this: If $[whatever, x - 1]$ is present in the set, remove it and add $[whatever, x]$. Likewise, if $[x + 1, whatever]$ is in the set, remove it and add $[x, whatever]$.

Removals are handled in this way: Find the interval containing x. Split it into two intervals $[start, x - 1]$, and $[x + 1, end]$.

MEX queries are handled similarly: Find the interval containing $x$ and output $end + 1$. This can be implemented using 2 std::set<std::pair<int, int>> in C++.
The first set indexes pairs by the first element (i.e. left end), and the second one by their second element (i.e. right end)

class MEX {
  typedef std::pair<int, int> interval;
  std::set<interval> s[2];
  std::multiset<int> values;
  void insert_pair(interval p) {
    auto[x, y] = p;
    if (x > y) std::swap(x, y);
    s[0].insert({x, y});
    s[1].insert({y, x});
  }
  void remove_pair(interval p) {
    auto[x, y] = p;
    if (x > y) std::swap(x, y);
    s[0].erase({x, y});
    s[1].erase({y, x});
  }
 
  std::optional<interval> is_end(int x, bool left) {
    int idx = left;
    auto it = s[idx].lower_bound({x, 0});
    if (it != s[idx].end() && it->first == x)
      return *it;
    else
      return std::nullopt;
  }
 
 public:
  void insert(int x) {
    bool ok = values.find(x) == values.end();
    values.insert(x);
    if (!ok) return;
    auto p1 = is_end(x - 1, true);
    auto p2 = is_end(x + 1, false);
    if (p1 && p2) {
      interval i = {p1->second, p2->second};
      remove_pair(*p1);
      remove_pair(*p2);
      insert_pair(i);
    } else if (p1 && !p2) {
      interval i = {p1->second, x};
      remove_pair(*p1);
      insert_pair(i);
    } else if (!p1 && p2) {
      interval i = {x, p2->second};
      remove_pair(*p2);
      insert_pair(i);
    } else if (!p1 && !p2) {
      interval i = {x, x};
      insert_pair(i);
    }
  }
  void remove(int x) {
    values.erase(values.find(x));
    if (values.find(x) != values.end()) return;
    auto it = s[1].lower_bound({x, 0});
    if (it->first != x && it->second != x) {
      interval p1 = {it->second, x - 1};
      interval p2 = {x + 1, it->first};
      remove_pair(*it);
      insert_pair(p1);
      insert_pair(p2);
    } else if (it->first != x && it->second == x) {
      interval p = {x + 1, it->first};
      remove_pair(*it);
      insert_pair(p);
    } else if (it->first == x && it->second == x) {
      remove_pair(*it);
    } else if (it->first == x && it->second != x) {
      interval p = {it->second, x - 1};
      remove_pair(*it);
      insert_pair(p);
    }
  }
  int get(int x) {
    if (values.find(x) == values.end()) return x;
    auto it = s[1].lower_bound({x, 0});
    return it->first + 1;
  }
};
  • Usage
MEX mex;
mex.insert(int);
mex.remove(int);
mex.get(int); // Find the minimum element >=x that isn't present in the set
$\endgroup$
2
  • $\begingroup$ Although here your $n$ is the largest integer and not the number of integers in the set right? $\endgroup$
    – Tassle
    Oct 10, 2020 at 19:59
  • $\begingroup$ @Tassle Yes, it means the Largest number. although you might not require a quite big number as MEX will be quite small. Even if input numbers are quite big. $\endgroup$ Oct 10, 2020 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.