Elimine duplicados en el propio array

Dado un arreglo ordenado, conserve una copia de cada valor sin usar otro arreglo. Hacerlo in situ ahorra memoria y es una pregunta clásica de las entrevistas. 🧹

Cuando el arreglo está ordenado, cada duplicado se encuentra justo al lado de su equivalente. Por eso solo necesita comparar vecinos, nunca todo el arreglo.

Use un puntero slow que marque el último valor conservado y un puntero fast que recorra el arreglo buscando algo nuevo.

Considere slow como la posición de escritura: todo lo que está en esa posición o antes ya está limpio y es único.

El puntero fast solo lee hacia delante. Avanza rápidamente y solo avisa a slow cuando encuentra un valor que aún no se ha conservado.

Si a[fast] es igual a a[slow], es una repetición, así que no haga nada salvo avanzar fast. El duplicado se omite discretamente.

Cuando a[fast] es diferente, avance slow y copie allí el nuevo valor. Así sobrescribe los duplicados antiguos con datos únicos nuevos.

Después del recorrido, slow + 1 es la cantidad de valores únicos, todos agrupados al principio del arreglo.

Todo lo que quede después del prefijo único son datos sobrantes. El problema solo considera los primeros elementos slow + 1, así que deje intacta la parte final.

Un arreglo vacío tiene cero valores únicos. Compruebe n == 0 antes de comenzar para no leer más allá del final.

Este patrón de punteros slow y fast se ejecuta en tiempo O(n) y usa O(1) de espacio adicional, exactamente lo que exigen los límites de memoria estrictos.

Está eliminando duplicados in situ en un arreglo ordenado con punteros slow y fast.

En un arreglo ordenado, un par de punteros lento-rápido elimina los duplicados en un recorrido O(n) sin espacio adicional y devuelve slow + 1 como cantidad de valores únicos. 🎉