Entrevista técnica: ¿Cómo encontrar la subsecuencia creciente más larga (LIS)?

Problema y escenarios de aplicación

Dado un arreglo de enteros nums, retorna cualquier subsecuencia estrictamente creciente más larga. Una subsecuencia preserva el orden relativo de la entrada pero no necesita ser contigua. "Estrictamente creciente" significa que cada valor siguiente debe ser mayor, por lo que los valores iguales no pueden aumentar la longitud. Si existen múltiples respuestas óptimas, retorna cualquiera de ellas. Retorna un arreglo vacío si la entrada está vacía.

Input:  [10, 9, 2, 5, 3, 7, 101, 18]
Output: [2, 3, 7, 18]

Increasing indices: 2 < 4 < 5 < 7
Increasing values:  2 < 3 < 7 < 18
Length: 4

Asume 0 ≤ n ≤ 100,000, valores enteros con signo de 32 bits y un arreglo de entrada que debe permanecer sin cambios. Esta escala descarta la enumeración de subsecuencias y descarta la programación dinámica cuadrática como la solución final. El problema de LeetCode solicita la longitud de una subsecuencia estrictamente creciente y plantea explícitamente un seguimiento con un objetivo de O(n log n). Un artículo público de preparación para entrevistas con fecha de abril de 2026 todavía enseña tanto la DP cuadrática como la optimización mediante búsqueda binaria. Esta versión retorna adicionalmente una subsecuencia real. Esas fuentes establecen el problema y su valor actual de preparación; no establecen la frecuencia en entrevistas ni la atribución a empresas específicas.

Qué evalúa el entrevistador

La primera señal es una definición de estado precisa. La solución cuadrática debe definir dp[i] como la mejor longitud que necesariamente termina en nums[i]. Decir únicamente "la respuesta para los primeros i valores" descarta el valor final necesario para decidir si el elemento actual puede ser añadido.

La segunda señal es derivar la optimización a partir del cuello de botella. Escanear cada j anterior para cada i cuesta O(n²). Una respuesta más sólida cambia el estado: para cada longitud alcanzable, conserva únicamente el menor valor de terminación. Una cola más pequeña es al menos igual de fácil de extender. Estas colas mínimas son estrictamente crecientes, por lo que la posición de actualización se puede encontrar mediante búsqueda binaria.

La tercera señal es el manejo correcto de duplicados. Una secuencia estrictamente creciente requiere la primera posición cuya cola sea mayor o igual que el valor actual: semántica de límite inferior (lower bound). Un valor igual reemplaza la misma posición y no extiende la longitud. Solo una variante no decreciente utiliza la primera posición estrictamente mayor que el valor.

La cuarta señal es saber que tails no es en sí mismo la respuesta. Después de [3, 5, 6, 2], los valores de cola son [2, 5, 6]. Aumentan en valor, pero sus índices de entrada son 3, 1, 2, por lo que no son una subsecuencia. Para retornar una ruta real, almacena también el índice de entrada actual para cada longitud de cola y un índice predecesor para cada elemento.

La señal final es la demostración y validación. Un candidato debe explicar el invariante de cola mínima, por qué el reemplazo no puede perder una longitud óptima, por qué los enlaces predecesores forman una ruta válida y cómo comparar entradas pequeñas aleatorias contra un oráculo de O(n²) en lugar de confiar en un solo ejemplo.

Preguntas para clarificar antes de responder

• ¿Estrictamente creciente o no decreciente? Este problema es estricto, por lo que los duplicados no pueden extender la respuesta. Si se permite la igualdad, el límite de la búsqueda binaria cambia.
• ¿Retornar la longitud o una secuencia real? Este problema retorna una secuencia, por lo que necesita previous e índices de colas. Una solución que solo devuelva la longitud puede reducir el espacio auxiliar a O(L), donde L es la longitud de la respuesta.
• ¿Cómo deben resolverse los empates entre respuestas óptimas? Cualquier respuesta es aceptable. Los requisitos de seleccionar la lexicográficamente menor, de menor índice o una selección estable necesitan reglas y demostraciones adicionales.
• ¿Cuál es el tamaño de la entrada? Con cien mil elementos, usa O(n log n). Para unos pocos cientos de elementos, la DP cuadrática es más fácil de implementar, explicar y extender al conteo.
• ¿Puede la entrada estar vacía? Sí; retorna []. Esto determina si la reconstrucción puede leer un índice de cola final.
• ¿Se puede modificar la entrada? No. Ordenar destruye el orden de índices original y cambia el problema.
• ¿Puede ocurrir desbordamiento aritmético de enteros? El algoritmo compara y copia valores sin realizar operaciones aritméticas sobre ellos, por lo que las entradas de 32 bits con signo no se desbordan debido al algoritmo.

Estructura de respuesta de 30 segundos

"Mantengo la cola más pequeña para cada longitud alcanzable. Esas colas están ordenadas, por lo que para cada valor busco binariamente la primera cola mayor o igual a él, reemplazo esa posición o la añado al final. Este límite inferior evita que los duplicados extiendan una secuencia estricta. El arreglo de colas puede mezclar índices de entrada incompatibles, por lo que también almaceno el índice de cada cola y un predecesor por cada elemento, para luego reconstruir hacia atrás. Una búsqueda binaria por elemento da un tiempo de O(n log n) y un espacio de O(n). Pruebo arreglos vacíos, con duplicados, decrecientes y arreglos pequeños aleatorios contra un oráculo cuadrático."

Solución profunda paso a paso

Comencemos con la base que es más fácil de demostrar. Sea dp[i] la longitud de una subsecuencia estrictamente creciente más larga que debe terminar en nums[i]. Cualquier respuesta mayor que uno tiene un penúltimo elemento en algún j < i con nums[j] < nums[i]:

dp[i] = 1 + max(dp[j]) over j < i and nums[j] < nums[i]
If no such j exists, dp[i] = 1
Final length = max(dp[i])

La definición también demuestra la recurrencia. Cada predecesor admisible puede ser extendido por nums[i], mientras que cada secuencia óptima que termina en nums[i] debe transicionar desde uno de esos predecesores. El problema es que cada i escanea todas las posiciones anteriores, para un tiempo total de O(n²).

Para la optimización, mantén este invariante de prefijo: después de procesar los primeros i elementos, tails[k] es el menor valor final posible entre todas las subsecuencias estrictamente crecientes de longitud k + 1. Para el valor actual x, localiza la primera posición que cumpla tails[k] ≥ x:

• Si no existe tal posición, x supera a todas las colas y extiende la secuencia más larga en uno.
• Si la posición k existe, reemplaza tails[k] con x. La longitud no cambia, pero una cola menor o igual no puede reducir las opciones de extensión futuras.
• Debido a que tails es estrictamente creciente, la posición se encuentra en tiempo O(log L).

Para [3, 5, 6, 2], los primeros tres estados son [3], [3, 5] y [3, 5, 6]. El 2 final reemplaza la primera posición, produciendo [2, 5, 6]. La longitud sigue siendo correcta, pero 2 ocurre después de 5 y 6 en la entrada. Este es el contraejemplo a retornar tails directamente.

La reconstrucción necesita dos estructuras de índices. tailsIndices[k] almacena la posición de entrada que actualmente materializa la cola mínima para la longitud k + 1. Cuando nums[i] cae en la posición k, establece previous[i] como tailsIndices[k - 1]. Ese predecesor ocurre antes de i y tiene un valor estrictamente menor. Los reemplazos de colas posteriores no mutan los enlaces predecesores ya escritos. Reconstruye hacia atrás desde la cola más larga final.

export function longestIncreasingSubsequence(nums: number[]): number[] {
  if (nums.length === 0) return []

  const tails: number[] = []
  const tailsIndices: number[] = []
  const previous = new Array<number>(nums.length).fill(-1)

  for (let index = 0; index < nums.length; index += 1) {
    const value = nums[index]
    let left = 0
    let right = tails.length

    while (left < right) {
      const middle = left + Math.floor((right - left) / 2)
      if (tails[middle] < value) left = middle + 1
      else right = middle
    }

    const lengthIndex = left
    if (lengthIndex > 0) {
      previous[index] = tailsIndices[lengthIndex - 1]
    }

    if (lengthIndex === tails.length) {
      tails.push(value)
      tailsIndices.push(index)
    } else {
      tails[lengthIndex] = value
      tailsIndices[lengthIndex] = index
    }
  }

  const result = new Array<number>(tails.length)
  let index = tailsIndices[tails.length - 1]

  for (
    let resultIndex = result.length - 1;
    resultIndex >= 0;
    resultIndex -= 1
  ) {
    result[resultIndex] = nums[index]
    index = previous[index]
  }

  return result
}

La correctitud consta de tres partes. Primero, tails permanece estrictamente creciente: eliminar el último elemento de una secuencia creciente más larga deja una secuencia más corta con una cola menor. Segundo, el reemplazo por búsqueda binaria preserva la cola realizable más pequeña para cada longitud; mejora la capacidad de extensión sin inventar una secuencia más larga. Tercero, cada tailsIndices[k] materializa una cadena de longitud k + 1, con índices predecesores y valores estrictamente crecientes. Por lo tanto, tails.length no puede exceder el verdadero óptimo, y escanear cualquier LIS real fuerza a la estructura a alcanzar al menos esa longitud. La cadena de predecesores reconstruida es una respuesta óptima válida.

Cada elemento realiza una búsqueda binaria sobre como máximo L colas, para un tiempo de O(n log L) y el límite superior convencional O(n log n). Los tres arreglos utilizan un espacio de O(n); la salida misma utiliza O(L). El algoritmo no ordena la entrada ni depende del rango numérico.

Las pruebas deben verificar la longitud, el incremento estricto y el orden de los índices de entrada:

const cases: Array<[number[], number]> = [
  [[10, 9, 2, 5, 3, 7, 101, 18], 4],
  [[0, 1, 0, 3, 2, 3], 4],
  [[7, 7, 7, 7], 1],
  [[5, 4, 3, 2, 1], 1],
  [[], 0],
]

for (const [nums, expectedLength] of cases) {
  const result = longestIncreasingSubsequence(nums)
  if (result.length !== expectedLength) throw new Error("wrong length")
  for (let i = 1; i < result.length; i += 1) {
    if (result[i - 1] >= result[i]) throw new Error("not increasing")
  }
}

Una verificación más sólida genera arreglos aleatorios de longitud como máximo 12 y compara la longitud del resultado optimizado con un oráculo DP de O(n²). Un escaneo lineal a través de la entrada también debe verificar que los valores retornados aparezcan en orden. Juntas, estas verificaciones exponen errores en límites de duplicados, condiciones de búsqueda binaria incorrectas y predecesores rotos.

Respuesta de muestra de alta calidad

"Primero confirmaré que el orden sea estricto y que deba retornar una secuencia real. La solución cuadrática define dp[i] como la mejor longitud que termina en nums[i] y verifica cada predecesor menor. Para eliminar ese escaneo hacia atrás, almaceno la menor cola posible para cada longitud.

Para un valor x, encuentro la primera cola mayor o igual a x. Si no existe ninguna, x extiende la secuencia más larga actual. De lo contrario, reemplazar esa cola con x da a esa misma longitud un valor que es al menos igual de fácil de extender. El incremento estricto requiere esta posición de límite inferior (lower bound), por lo que un duplicado reemplaza en lugar de extender.

Los valores de cola resumen la mejor terminación para cada longitud; no necesariamente provienen de índices de entrada compatibles. Para retornar una respuesta real, tailsIndices[k] registra el índice de cola actual para la longitud k + 1. Cuando un elemento cae en la posición k, su predecesor es tailsIndices[k - 1]. Después del escaneo, sigo los predecesores desde la cola más larga y lleno la salida hacia atrás.

El invariante es que cada cola es la menor cola realizable para su longitud, y cada índice de cola tiene una cadena de predecesores real. El reemplazo nunca elimina una longitud existente y solo mejora extensiones futuras. A la inversa, escanear cada elemento de cualquier subsecuencia creciente real fuerza a la estructura a alcanzar al menos esa longitud, por lo que la longitud final es óptima. Una búsqueda binaria por elemento da un tiempo de O(n log n), y los índices más los predecesores usan un espacio de O(n). Probaría entradas vacías, con duplicados, crecientes y decrecientes, y luego compararía arreglos pequeños aleatorios con un oráculo cuadrático."

Errores comunes

• Tratar una subsecuencia como un subarreglo contiguo → Una ventana deslizante no puede saltar elementos → Define la respuesta mediante índices de entrada crecientes.
• Ordenar antes de resolver → Ordenar destruye el orden relativo original → Procesa los valores en el orden de entrada.
• Definir dp[i] como un óptimo de prefijo y transicionar directamente → La cola del óptimo podría no aceptar el valor actual → Exige que el estado termine en i.
• Buscar la primera cola estrictamente mayor que el valor en la variante estricta → Los duplicados extienden incorrectamente la longitud → Busca la primera cola mayor o igual al valor.
• Retornar tails directamente → Los valores de cola pueden provenir de índices de entrada decrecientes → Reconstruye con índices de cola y enlaces predecesores.
• Reescribir predecesores antiguos tras un reemplazo de cola → Se corrompe una ruta previamente válida → Mantén cada predecesor inmutable después de su asignación.
• Demostrar únicamente que las colas están ordenadas → Que estén ordenadas por sí solo no demuestra una longitud óptima → Demuestra el invariante de cola mínima realizable y ambos límites de longitud.
• Llamar a búsqueda binaria más inserción en arreglo O(log n) → La inserción intermedia desplaza elementos → Solo reemplaza en la posición (in-place) o añade al final.
• Ejecutar solo el ejemplo clásico → Los errores con duplicados y predecesores permanecen ocultos → Usa pruebas con todos los elementos iguales, decrecientes, vacíos y oráculos aleatorizados.
• Afirmar una alta frecuencia en una empresa nombrada → Las páginas públicas de problemas no demuestran frecuencia ni atribución → Menciona solo el valor verificado del problema y del algoritmo.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Qué cambia para una subsecuencia no decreciente más larga?

Los valores iguales ahora pueden extender la secuencia. Cambia el límite a la primera posición estrictamente mayor que value, que es el punto de inserción derecho. Los predecesores, la reconstrucción y la complejidad siguen siendo los mismos. Cambiar únicamente la comparación final sin cambiar el límite de la búsqueda binaria falla con los duplicados.

Pregunta de seguimiento 2: ¿Puede una respuesta de solo longitud usar menos espacio?

Sí. Elimina tailsIndices y previous, y conserva solo los L valores mínimos de cola para un espacio de O(L). El tiempo sigue siendo O(n log L). Retornar una secuencia ya requiere una salida de O(L), mientras que esta reconstrucción en una sola pasada utiliza la información de predecesores para cada posición de entrada.

Pregunta de seguimiento 3: ¿Cómo se cuenta el número de subsecuencias crecientes más largas?

Las colas mínimas combinan múltiples rutas de la misma longitud, por lo que no pueden recuperar conteos directamente. Una solución simple mantiene length[i] y count[i]: copia el conteo del predecesor cuando se encuentra una ruta más larga y suma los conteos cuando se encuentra una ruta de igual longitud, con un tiempo de O(n²). Para entradas más grandes se pueden comprimir coordenadas y utilizar un árbol de Fenwick o árbol de segmentos que almacene el par de longitud máxima y conteo, con reglas de fusión cuidadosas para evitar el doble conteo.

Pregunta de seguimiento 4: ¿Qué ocurre si los valores llegan en un flujo de solo adición (append-only stream)?

La longitud actual de la LIS es en línea: busca binariamente en tails para cada valor que llega en tiempo O(log L). Conserva índices y predecesores si debe haber una secuencia real disponible. Si se pueden eliminar valores antiguos, una cola mínima puede depender de datos eliminados; este algoritmo no puede deshacer ese estado localmente, por lo que se necesitarían estructuras dinámicas o descomposición fuera de línea (offline).

Pregunta de seguimiento 5: ¿Qué pasa si cada elemento tiene un peso y el objetivo es el peso total máximo?

Una cola mínima ya no resume el estado porque el mismo rango de colas puede llevar diferentes pesos acumulados. Comprime las coordenadas de los valores, consulta un árbol de Fenwick o árbol de segmentos para obtener el mejor peso entre los valores menores, suma el peso actual y actualiza la coordenada actual. Las variantes estricta y no decreciente siguen usando diferentes límites de consulta. El tiempo es O(n log n).

Pregunta de seguimiento 6: ¿Este código retorna la respuesta óptima lexicográficamente menor?

No lo garantiza. La regla de reemplazo minimiza valores de cola individuales, pero no define un orden estable entre rutas óptimas completas. Un enfoque calcula cuánto prefijo o sufijo óptimo puede soportar cada índice, y luego selecciona vorazmente los valores que aún pueden completar una respuesta de longitud óptima. Una secuencia de menor valor y una secuencia de menor índice son requisitos diferentes, por lo que primero aclara a qué orden lexicográfico se hace referencia.