1.2.8 Minimum Excluded Value

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

/*

Computes the minimum excluded nonnegative integer, commonly called the MEX. The MEX of a set is the
smallest integer $x \geq 0$ that does not appear in the set. It appears frequently in array
problems, game theory with Grundy numbers, and dynamic programming states. Since the MEX of $n$
elements never exceeds $n$, the one-shot version simply marks which of the values $0$ to $n$ occur
and scans for the first gap. The dynamic version keeps a count per value plus an ordered set of
absent values, whose smallest member is always the current MEX.

- `mex(lo, hi)` returns the MEX of the values in [`lo`, `hi`).
- `DynamicMex(n)` maintains counts of values in [0, `n`], enough to track the MEX of a multiset of
  at most `n` relevant nonnegative values.
- `add(x)` inserts one copy of value `x` if `x` $\in$ [0, `n`].
- `remove(x)` removes one copy of value `x` if present.
- `get()` returns the current MEX.

Time Complexity:
- O(n) per call to `mex(lo, hi)`, where $n$ is the number of values.
- O(log n) per call to `add(x)`, `remove(x)`, and `get()` for `DynamicMex`.

Space Complexity:
- O(n) auxiliary heap space for both approaches.

*/

#include <set>
#include <vector>

template<class It>
int mex(It lo, It hi) {
  int n = static_cast<int>(hi - lo);
  std::vector<bool> seen(n + 1, false);
  for (It it = lo; it != hi; ++it) {
    if (0 <= *it && *it <= n) {
      seen[*it] = true;
    }
  }
  for (int x = 0; x <= n; x++) {
    if (!seen[x]) {
      return x;
    }
  }
  return n + 1;
}

class DynamicMex {
  std::vector<int> count;
  std::set<int> missing;

 public:
  explicit DynamicMex(int n) : count(n + 1, 0) {
    for (int x = 0; x <= n; x++) {
      missing.insert(x);
    }
  }

  void add(int x) {
    if (0 <= x && x < static_cast<int>(count.size()) && count[x]++ == 0) {
      missing.erase(x);
    }
  }

  void remove(int x) {
    if (0 <= x && x < static_cast<int>(count.size()) && count[x] > 0 && --count[x] == 0) {
      missing.insert(x);
    }
  }

  int get() const { return *missing.begin(); }
};

/*** Example Usage ***/

#include <cassert>
using namespace std;

int main() {
  vector<int> a{0, 1, 4, 2, 1};
  assert(mex(a.begin(), a.end()) == 3);

  DynamicMex m(5);
  m.add(0);
  m.add(1);
  m.add(3);
  assert(m.get() == 2);
  m.add(2);
  assert(m.get() == 4);
  m.remove(1);
  assert(m.get() == 1);
  return 0;
}