MEX (mínimo excluido) de una secuencia

Dado un arreglo $A$ de tamaño $N$ . Hay que encontrar el menor elemento no negativo que no está presente en el arreglo. Ese número se llama habitualmente el MEX (minimal excluded / mínimo excluido).

$\begin{aligned} mex ({0, 1, 2, 4, 5}) & = 3 \\ mex ({0, 1, 2, 3, 4}) & = 5 \\ mex ({1, 2, 3, 4, 5}) & = 0 \end{aligned}$

Nótese que el MEX de un arreglo de tamaño $N$ nunca puede ser mayor que $N$ mismo.

El enfoque más fácil es crear un conjunto de todos los elementos del arreglo $A$ , para poder chequear rápido si un número está en el arreglo o no. Después podemos chequear todos los números de $0$ a $N$ : si el número actual no está en el conjunto, devolverlo.

Implementación

El siguiente algoritmo corre en tiempo $O(N \log N)$ .


int mex(vector<int> const& A) {
    set<int> b(A.begin(), A.end());

    int result = 0;
    while (b.count(result))
        ++result;
    return result;
}

Si un algoritmo requiere un cómputo de MEX en $O(N)$ , es posible usando un vector booleano en lugar de un conjunto. Nótese que el arreglo tiene que ser tan grande como el mayor tamaño posible de arreglo.


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

    // mark the given numbers
    for (int x : A) {
        if (x <= MAX_N)
            used[x] = true;
    }

    // find the mex
    int result = 0;
    while (used[result])
        ++result;
 
    // clear the array again
    for (int x : A) {
        if (x <= MAX_N)
            used[x] = false;
    }

    return result;
}

Este enfoque es rápido, pero solo funciona bien si hay que computar el MEX una vez. Si hay que computar el MEX una y otra vez, p. ej. porque el arreglo sigue cambiando, entonces no es efectivo. Para eso necesitamos algo mejor.

MEX con actualizaciones del arreglo

En el problema hay que cambiar números individuales del arreglo y computar el nuevo MEX del arreglo después de cada actualización.

Hace falta una estructura de datos mejor que maneje esas consultas de forma eficiente.

Un enfoque sería tomar la frecuencia de cada número de $0$ a $N$ y construir encima una estructura de datos tipo árbol. P. ej. un Árbol de Segmentos o un Treap. Cada nodo representa un rango de números, y además de la frecuencia total en el rango, se guarda la cantidad de números distintos en ese rango. Es posible actualizar esta estructura en $O(\log N)$ , y también encontrar el MEX en $O(\log N)$ , haciendo una búsqueda binaria del MEX. Si el nodo que representa el rango $[0, \lfloor N/2 \rfloor)$ no contiene $\lfloor N/2 \rfloor$ números distintos, entonces falta uno y el MEX es menor que $\lfloor N/2 \rfloor$ , y se puede recurrir por la rama izquierda del árbol. Si no, es al menos $\lfloor N/2 \rfloor$ , y se puede recurrir por la rama derecha.

También es posible usar las estructuras de la biblioteca estándar map y set (basado en un enfoque explicado acá ). Con un map recordamos la frecuencia de cada número, y con el set representamos los números que actualmente faltan en el arreglo. Como un set está ordenado, *set.begin() será el MEX. En total necesitamos $O(N \log N)$ de precomputación, y después el MEX se puede computar en $O(1)$ y una actualización se puede hacer en $O(\log N)$ .


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 <= 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 (mínimo excluido) de una secuencia

Implementación

MEX con actualizaciones del arreglo

Problemas de práctica