1.7.1 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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

/*

Given a multiset of integers, find the minimum excluded nonnegative value (MEX), i.e. the smallest
integer $x \geq 0$ not present in the multiset. MEX often appears in array problems, game theory
with Grundy numbers, and dynamic programming states. Since the MEX of $n$ values never exceeds $n$,
the one-shot version tracks seen values in $[0, n]$ before scanning to find the first missing.

- `mex(lo, hi)` returns the MEX of the values in $[`lo`, `hi`)$.

The MEX of a dynamic multiset can be computed using counts of present values and maintaining an
ordered set of currently missing candidates.

- `DynamicMex()` maintains the MEX of a multiset of nonnegative integers.
- `add(x)` inserts one copy of value `x` if `x` $\geq 0$.
- `remove(x)` removes one copy of value `x` if present.
- `mex()` returns the current MEX.

Time Complexity:
- O(n) per call to `mex(lo, hi)`, where $n$ is the number of values.
- O(log n) expected per call to `add(x)` and `remove(x)` for `DynamicMex`, and O(n) in the
  collision-heavy worst case for the hash table.
- O(1) per call to `mex()` for `DynamicMex`.

Space Complexity:
- O(n) auxiliary for `mex(lo, hi)`.
- O(n) storage for `DynamicMex`.

*/

#include <iterator>
#include <set>
#include <unordered_map>
#include <vector>

template<typename It>
int mex(It lo, It hi) {
  int n = std::distance(lo, hi);
  std::vector<char> seen(n + 1);
  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::unordered_map<int, int> count;
  std::set<int> missing;  // Missing candidates in [0, size].
  int size = 0;

 public:
  DynamicMex() { missing.insert(0); }

  void add(int x) {
    if (x < 0) {
      return;
    }
    if (!count.count(size + 1)) {
      missing.insert(size + 1);
    }
    if (count[x]++ == 0) {
      missing.erase(x);
    }
    size++;
  }

  void remove(int x) {
    auto it = count.find(x);
    if (it == count.end()) {
      return;
    }
    bool removed_last = --it->second == 0;
    if (removed_last) {
      count.erase(it);
    }
    size--;
    missing.erase(size + 1);
    if (removed_last && x <= size) {
      missing.insert(x);
    }
  }

  int mex() 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);
  vector<int> b{-1, 0, 1, 2};
  assert(mex(b.begin(), b.end()) == 3);  // Negative values are ignored.

  DynamicMex m;
  m.add(0);
  m.add(1);
  m.add(1);
  m.add(3);
  assert(m.mex() == 2);
  m.add(2);
  assert(m.mex() == 4);
  m.remove(1);
  assert(m.mex() == 4);  // One copy of 1 remains.
  m.remove(1);
  assert(m.mex() == 1);
  m.remove(100);
  assert(m.mex() == 1);
  return 0;
}