Mex
(algo/sequence/mex.hpp)

• View this file on GitHub
• Last update: 2026-10-06 02:15:41+09:00
• Include: #include "algo/sequence/mex.hpp"

Overview

mex(values) returns the smallest nonnegative integer absent from an integer vector. For example, the mex of 0, 1, 1, 3 is 2. The empty vector has mex 0.

Interface

Exact signature	Description	Complexity
template <class T> int mex(const std::vector<T>& values)	Returns the mex without modifying values.	$O(N)$ time and $O(N)$ auxiliary space

T must be a standard integral type, signed or unsigned. The vector length N must fit in int; this is checked by an assertion. Duplicates, negative values, and values at least N do not affect the answer. The result is always in [0, N]. The implementation uses a byte per candidate and does not sort the input.

For repeated queries with insertions and deletions, use MexMultiset.

Example

#include "algo/sequence/mex.hpp"

#include <iostream>
#include <vector>

int main() {
    std::vector<long long> values = {3, 0, 1, 1, -5, 1000000000000LL};
    std::cout << m1une::algo::mex(values) << '\n';  // 2
}

Required by

• Algorithms All (algo/all.hpp)
• Sequence Algorithms All (algo/sequence/all.hpp)

Verified with

• verify/ds/bst/mex_multiset.test.cpp

Code

#ifndef M1UNE_ALGO_SEQUENCE_MEX_HPP
#define M1UNE_ALGO_SEQUENCE_MEX_HPP 1

#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <vector>

namespace m1une {
namespace algo {

// Returns the smallest nonnegative integer absent from values.
template <class T>
int mex(const std::vector<T>& values) {
    static_assert(
        std::is_integral_v<T> && sizeof(T) <= sizeof(std::uintmax_t),
        "mex requires standard integral values"
    );
    assert(values.size() <= static_cast<std::size_t>(std::numeric_limits<int>::max()));
    const int n = int(values.size());
    std::vector<unsigned char> present(n, 0);
    for (T value : values) {
        if constexpr (std::is_signed_v<T>) {
            if (value < 0) continue;
        }
        if (static_cast<std::uintmax_t>(value) < static_cast<std::uintmax_t>(n)) {
            present[int(value)] = 1;
        }
    }
    int answer = 0;
    while (answer < n && present[answer]) ++answer;
    return answer;
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_SEQUENCE_MEX_HPP

#line 1 "algo/sequence/mex.hpp"



#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <vector>

namespace m1une {
namespace algo {

// Returns the smallest nonnegative integer absent from values.
template <class T>
int mex(const std::vector<T>& values) {
    static_assert(
        std::is_integral_v<T> && sizeof(T) <= sizeof(std::uintmax_t),
        "mex requires standard integral values"
    );
    assert(values.size() <= static_cast<std::size_t>(std::numeric_limits<int>::max()));
    const int n = int(values.size());
    std::vector<unsigned char> present(n, 0);
    for (T value : values) {
        if constexpr (std::is_signed_v<T>) {
            if (value < 0) continue;
        }
        if (static_cast<std::uintmax_t>(value) < static_cast<std::uintmax_t>(n)) {
            present[int(value)] = 1;
        }
    }
    int answer = 0;
    while (answer < n && present[answer]) ++answer;
    return answer;
}

}  // namespace algo
}  // namespace m1une

Back to top page