Distancia de la repetición más cercana
La misión
Problema
Recibes una lista de valores. Entre todos los pares de posiciones que guardan el mismo valor, encuentra el par que está más cerca y devuelve la distancia entre ellos, medida como la diferencia de sus índices. Si ningún valor aparece dos veces, devuelve -1.
Ejemplos
Input: values = [7, 1, 3, 7, 1, 7]
Output: 2
Por qué: los 7 en los índices 3 y 5 están a dos de distancia; los 1, a tres
Input: values = [3, 8, 8, 3]
Output: 1
Por qué: los dos 8 están uno al lado del otro
Input: values = [5, 6, 7]
Output: -1
Por qué: caso límite: nada se repite
Pistas
0 / 3
Comparar cada par de posiciones funciona, pero el trabajo crece con el cuadrado de la longitud: si duplicas la lista, tarda cuatro veces más.
Para el valor de la posición actual, solo una posición anterior puede dar la menor distancia. ¿Cuál es, y qué te permitiría encontrarla al instante?
Recorre la lista una vez, manteniendo un mapa de cada valor al último índice donde lo viste. Cuando el valor actual ya está en el mapa, compara el índice actual menos el guardado con la mejor distancia hasta ahora, y luego sobrescribe el índice guardado.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Solución
El gemelo anterior más cercano de cualquier posición es el más reciente, así que basta con recordar el último índice de cada valor. Un hash map (tabla hash de pares clave-valor) responde esa búsqueda en tiempo constante en promedio, lo que convierte la comprobación cuadrática de pares en una sola pasada. El mapa se actualiza después de cada paso, así que siempre guarda el índice más reciente de cada valor. El tiempo es O(n) en promedio, y el espacio es O(n) para el mapa.
def closest_repeat(values):
last_seen = {} # value -> most recent index
best = -1
for i, v in enumerate(values):
if v in last_seen:
gap = i - last_seen[v]
if best == -1 or gap < best:
best = gap
last_seen[v] = i # only the latest index can matter later
return best
print(closest_repeat([7, 1, 3, 7, 1, 7])) # -> 2
print(closest_repeat([3, 8, 8, 3])) # -> 1
print(closest_repeat([5, 6, 7])) # -> -1¿Lo que te frena es la idea y no el código? ¿Qué es Big-O? lo explica.