MEX (Minimal Excluded)

Given an array A of size N, the MEX is the smallest non-negative integer that does not appear in A.

mex({0, 1, 2, 4, 5}) = 3
mex({0, 1, 2, 3, 4}) = 5
mex({1, 2, 3, 4, 5}) = 0

Bound: for an array of length N, mex(A) ≤ N (the values 0…N−1 cannot all be present if the mex were > N).

This lesson follows CP-Algorithms — MEX.

One-shot: set — O(N log N)

Put all elements in a set, then walk result = 0, 1, 2, … until a value is missing.

int mex(vector<int> const& A) {
    set<int> b(A.begin(), A.end());
    int result = 0;
    while (b.count(result))
        ++result;
    return result;
}

One-shot: boolean mark — O(N)

Mark presence in a bool array of size N+1 (values > N cannot affect the mex). Clear flags afterward if you reuse a static buffer.

int mex(vector<int> const& A) {
    static bool used[MAX_N + 1] = {0};

    for (int x : A) {
        if (x <= MAX_N)
            used[x] = true;
    }

    int result = 0;
    while (used[result])
        ++result;

    for (int x : A) {
        if (x <= MAX_N)
            used[x] = false;
    }
    return result;
}

Great for a single query. Painful if A keeps changing and you recompute from scratch every time.

🧪 One-shot MEX (C++)

MEX with updates

Need point updates A[idx] ← new_value and a fast mex after each change.

Segment tree / treap on frequencies

Store frequencies of values 0…N. Each node also tracks how many distinct values appear in its range. Update in O(log N).

Find mex with a tree walk / binary search:

• If the left half [0, ⌊N/2⌋) has fewer than ⌊N/2⌋ distinct values, a hole exists on the left → go left.
• Else every value in the left half is present → mex ≥ ⌊N/2⌋ → go right.

map + set — mex in O(1), update O(log N)

• frequency[x] = how often x appears
• missing_numbers = all currently absent values in 0…N (ordered set)
• mex = *missing_numbers.begin()

Precompute in O(N log N). On update: if an old value’s frequency hits 0, insert it into missing; erase the new value from missing.

class Mex {
private:
    map<int, int> frequency;
    set<int> missing_numbers;
    vector<int> A;

public:
    Mex(vector<int> const& A) : A(A) {
        for (int i = 0; i <= (int)A.size(); i++)
            missing_numbers.insert(i);
        for (int x : A) {
            ++frequency[x];
            missing_numbers.erase(x);
        }
    }

    int mex() {
        return *missing_numbers.begin();
    }

    void update(int idx, int new_value) {
        if (--frequency[A[idx]] == 0)
            missing_numbers.insert(A[idx]);
        A[idx] = new_value;
        ++frequency[new_value];
        missing_numbers.erase(new_value);
    }
};

🧪 Mex class with updates

Check: MEX basics

Quiz

MEX basics

1 / 4

mex({1,2,3,4,5}) equals…

Pick an answer to see if you are right.

Practice drills

Activity: Compute MEX

First line: n. Second: n ints. Print mex(A).

Contest problems

From CP-Algorithms:

• AtCoder HHKB2020 C — Neq Min
• Codeforces 1935B — Informatics in MAC
• Codeforces 1375D — Replace by MEX
• Codeforces 842D — Vitya and Strange Lesson
• Codeforces 817F — MEX Queries

Cheat sheet

Idea	Takeaway
Definition	Smallest missing ≥ 0
Bound	mex ≤ N
One-shot set	O(N log N)
One-shot bool	O(N)
Updates	Freq + missing set, or segtree on distinct counts
Fast mex	*missing.begin() in O(1)
Update	O(log N)