Longest Consecutive Sequence

Q: ¿Cuál es la complejidad temporal de la secuencia consecutiva más larga?

La solución con un conjunto hash se ejecuta en tiempo O(n) en promedio y usa memoria adicional O(n) . Ordenar y después contar las secuencias lleva un tiempo de O(n log n) . Buscar en el arreglo cada valor siguiente sin un conjunto puede llevar hasta O(n³) .

Q: ¿Puede union-find resolver la secuencia consecutiva más larga?

Sí. Convierte cada valor distinto en un conjunto, une x con x+1 siempre que ambos estén presentes y devuelve el tamaño del conjunto más grande. Se ejecuta en un tiempo cercano a O(n) , pero necesita un mapa de valores a índices, enlaces a los padres y tamaños, mientras que el recorrido con un conjunto hash hace el mismo trabajo con un conjunto y dos bucles.

MedioHashing

+10

Recibes un arreglo de enteros nums sin ningún orden particular. Una secuencia consecutiva es un grupo de valores x, x+1, x+2 y así sucesivamente, cada uno de los cuales aparece en algún lugar de nums. Devuelve la longitud de la secuencia consecutiva más larga. Un valor que aparece más de una vez cuenta una sola vez.

Función

longestConsecutive(nums: integer-array) → integer

numsinteger-array: los números enteros, en cualquier orden; se permiten repeticiones
Devuelveinteger: la longitud de la racha más larga de valores consecutivos presentes en nums

Restricciones

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Los valores pueden repetirse. Las posiciones en el arreglo no importan; solo importa qué valores están presentes.

Ejemplos

Entrada: nums = [40, 4, 39, 1, 3, 2, 41]
Salida: 4
Explicación: 1, 2, 3 y 4 están todos presentes, una secuencia de 4, aunque estén dispersos por la matriz. La otra secuencia, de 39 a 41, solo tiene 3 valores.

Entrada: nums = [7, 3, 7, 5, 6, 5]
Salida: 3
Explicación: 5, 6 y 7 forman una secuencia de 3. El segundo 7 y el segundo 5 no aportan nada, y 3 no puede unirse porque falta 4.

+17 pruebas ocultas al enviar

Para ir más allá

Supón que los valores llegan uno a uno y que, después de cada uno, debes informar de la secuencia más larga hasta ese momento. ¿Puedes mantener la respuesta actualizada en un tiempo promedio de O(1) por valor?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Los valores de una secuencia pueden estar en cualquier lugar del arreglo, así que no puedes leer las secuencias de izquierda a derecha. Ordenar los alinea en O(n log n). Un conjunto hash funciona mejor: responde «¿está aquí x+1?» en O(1), y si cuentas solo a partir de los valores cuyo x-1 no está, se recorre cada valor una sola vez, lo que hace que toda la búsqueda sea O(n).

Cuenta hacia arriba desde cada valor buscando en el array

Correcto, pero no termina con las pruebas más grandes

Intuición

Trata cada valor como el posible inicio de una secuencia. Desde x, busca x+1 en el arreglo; si está, busca x+2 y sigue hasta que falte un valor. La cantidad de valores alcanzados es la secuencia que empieza en x, y la mayor de estas longitudes es la respuesta.

Es correcto porque cada secuencia tiene un valor mínimo, ese valor está en nums, y el bucle lo prueba como inicio y recorre toda la secuencia. Las repeticiones no perjudican: solo prueban el mismo inicio dos veces.

Es lento por dos motivos. Cada búsqueda de «¿está aquí?» lee hasta n valores, y una secuencia larga se recorre de nuevo desde cada uno de sus elementos. Toma 10^4 valores que forman una secuencia desordenada: los recorridos suman aproximadamente n²/2 = 5 × 10^7 pasos, y cada paso examina en promedio la mitad del arreglo. Eso equivale a alrededor de 2.5 × 10^11 comparaciones.

Algoritmo

Establece best en 0.
Para cada valor start en nums, establece current en start y length en 1.
Mientras un recorrido de nums encuentre current+1, suma 1 a current y a length.
Guarda length en best si es mayor.
Devuelve best.

def longestConsecutive(nums):
    best = 0
    for start in nums:
        current = start
        length = 1
        # "in" on a list reads it from the front until it finds the value.
        while current + 1 in nums:
            current += 1
            length += 1
        best = max(best, length)
    return best

Ordena y después cuenta las secuencias

Intuición

La ordenación coloca los valores de cada secuencia uno junto al otro. [40, 4, 39, 1, 3, 2, 41] se convierte en [1, 2, 3, 4, 39, 40, 41], y las secuencias se leen de izquierda a derecha: de 1 a 4, después un salto hasta 39.

Recorre los valores ordenados y lleva la cuenta de la longitud de la secuencia actual. Un valor que supera en uno al anterior la prolonga. Un valor igual al anterior es una repetición: sáltalo, porque no prolonga ni termina la secuencia. Cualquier otro valor es un hueco, y allí comienza una nueva secuencia de longitud 1.

La ordenación cuesta O(n log n) y el recorrido, O(n). Ordenar en el mismo sitio no requiere ningún arreglo adicional, pero reordena la entrada de quien llama; los lenguajes que ordenan una copia usan O(n) de memoria.

Algoritmo

Ordena nums en orden creciente.
Establece best y run en 1, ya que el arreglo nunca está vacío.
Para cada índice i a partir de 1, omite nums[i] si es igual a nums[i-1].
Si nums[i] es nums[i-1]+1, suma 1 a run; de lo contrario, establece run en 1. Guarda run en best si es mayor.
Devuelve best.

def longestConsecutive(nums):
    nums.sort()
    best = 1
    run = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            continue  # a repeat neither extends nor breaks the run
        if nums[i] == nums[i - 1] + 1:
            run += 1
        else:
            run = 1
        best = max(best, run)
    return best

Conjunto hash, contando solo desde el inicio de cada ejecución

Intuición

Coloca cada valor en un conjunto hash. Ahora, «¿está presente x+1?» cuesta O(1) en promedio en lugar de hacer un recorrido, y los valores repetidos se reducen a una sola entrada.

Recorrer desde cada valor seguiría repitiendo trabajo: en la secuencia 1, 2, 3, 4, darías 3 pasos desde 1, 2 desde 2 y 1 desde 3. Así que inicia un recorrido solo desde el primer valor de una secuencia. Un valor x es el primero exactamente cuando x-1 no está en el conjunto. En [40, 4, 39, 1, 3, 2, 41], solo 1 y 39 cumplen esta condición: desde 1 llegas hasta 4, una longitud de 4, y desde 39 llegas hasta 41, una longitud de 3.

Cada valor pertenece exactamente a una secuencia, y solo el recorrido desde el primer valor de esa secuencia pasa por él, así que todos los recorridos juntos dan como máximo n pasos. Añade una comprobación de pertenencia por cada valor y la creación del conjunto, y el total es de O(n) en tiempo y O(n) de memoria para el conjunto.

Recorre el conjunto, no nums. Si el primer valor de una secuencia de 2,500 valores aparece 2,000 veces en nums, recorrer nums hace que recorras esa secuencia 2,000 veces.

Algoritmo

Coloca cada valor de nums en un conjunto hash values y establece best en 0.
Para cada valor x del conjunto, sáltatelo si x-1 está en el conjunto: no es el primer valor de su secuencia.
De lo contrario, establece end en x y súmale 1 mientras end+1 esté en el conjunto.
Guarda end-x+1 en best si es mayor.
Devuelve best.

def longestConsecutive(nums):
    values = set(nums)
    best = 0
    for value in values:
        # Only a value with no left neighbour starts a run.
        if value - 1 in values:
            continue
        end = value
        while end + 1 in values:
            end += 1
        best = max(best, end - value + 1)
    return best

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben a los valores repetidos, y la mayoría de las respuestas lentas, a recorrer la misma secuencia más de una vez.

Tratar un valor repetido como un hueco o como un paso después de ordenar. En [1, 2, 2, 3], reiniciar la secuencia en el segundo 2 da 2, y contarlo como un paso da 4. La respuesta es 3.
Inicializar best en 0 en el recorrido ordenado y actualizarlo solo dentro del bucle. Así, un arreglo con un solo valor devuelve 0 en vez de 1.
Recorrer todos los valores del conjunto en lugar de empezar solo en los inicios de las secuencias. La respuesta es correcta, pero una secuencia de 10^4 valores requiere 5 × 10^7 pasos: el trabajo cuadrático que se suponía que el conjunto eliminaría.
Recorrer nums en lugar del conjunto cuando hay valores repetidos. La secuencia que empieza en un valor que aparece miles de veces se recorre miles de veces.
Marcar los valores en un arreglo indexado por valor. Los valores llegan a ±10^9, así que el arreglo necesitaría 2 × 10^9 entradas.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de la secuencia consecutiva más larga?

La solución con un conjunto hash se ejecuta en tiempo O(n) en promedio y usa memoria adicional O(n). Ordenar y después contar las secuencias lleva un tiempo de O(n log n). Buscar en el arreglo cada valor siguiente sin un conjunto puede llevar hasta O(n³).

¿Por qué la solución con un conjunto hash es O(n) cuando tiene un bucle while dentro de un bucle for?

El bucle interno solo se ejecuta desde un valor cuyo vecino a la izquierda x-1 no está presente, es decir, el primer valor de su secuencia. Cada valor se recorre durante el recorrido de su propia secuencia y durante ningún otro recorrido, así que todos los bucles internos juntos realizan como máximo n pasos. El bucle externo añade una comprobación por cada valor, para un total de O(n).

¿Puedes resolver la secuencia consecutiva más larga sin memoria adicional?

Sí, si puedes reordenar la entrada: ordénala en el mismo sitio y cuenta las secuencias en una sola pasada, omitiendo las repeticiones. Eso usa O(1) de memoria adicional, pero tarda O(n log n). La solución O(n) necesita el conjunto hash.

¿Puede union-find resolver la secuencia consecutiva más larga?

Sí. Convierte cada valor distinto en un conjunto, une x con x+1 siempre que ambos estén presentes y devuelve el tamaño del conjunto más grande. Se ejecuta en un tiempo cercano a O(n), pero necesita un mapa de valores a índices, enlaces a los padres y tamaños, mientras que el recorrido con un conjunto hash hace el mismo trabajo con un conjunto y dos bucles.

Python

def longestConsecutive(nums):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

nums = [40, 4, 39, 1, 3, 2, 41]

Esperado

Longest Consecutive Sequence

Función

Restricciones

Ejemplos

Pistas

Solución

Cuenta hacia arriba desde cada valor buscando en el array

Ordena y después cuenta las secuencias

Conjunto hash, contando solo desde el inicio de cada ejecución

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares