Entrevista técnica: ¿Cómo resolver Trapping Rain Water con dos punteros?

Problema y escenarios aplicables

Dado un arreglo de enteros no negativos height de longitud n, height[i] es la altura de la barra en el índice i, y cada barra tiene un ancho de 1. Calcula el agua de lluvia total atrapada por estas barras. Por ejemplo:

height = [4, 2, 0, 3, 2, 5]
result = 9

El objetivo es un tiempo de O(n) y un espacio auxiliar de O(1). Las restricciones estándar son 1 <= n <= 20000 y 0 <= height[i] <= 100000. Las alturas nunca son negativas, y el problema principal no solicita el agua almacenada sobre cada barra individual.

Existe evidencia pública directa de entrevistas para esta pregunta. Un informe de junio de 2025 de una entrevista de pasantía de backend en Go en Baidu menciona Trapping Rain Water como una de tres tareas de código en vivo. Otro informe público de filtro telefónico agrega una variante en la que se vierte una cantidad finita de agua en una posición seleccionada. Las páginas del problema en LeetCode en inglés y chino lo clasifican como difícil y lo etiquetan con arreglos, dos punteros, programación dinámica, pilas y pilas monotónicas. La habilidad central es derivar y demostrar un algoritmo lineal a partir de una fórmula local, por lo que la categoría es coding independientemente del lenguaje de implementación o el tipo de puesto.

Qué evalúa el entrevistador

Primero, ¿puedes formular la cantidad correcta sobre una barra? El nivel de agua en el índice i está limitado por la más baja entre la barra más alta a su izquierda y la barra más alta a su derecha, no por las dos barras vecinas. Si leftMax[i] y rightMax[i] incluyen ambos el índice i, la cantidad es min(leftMax[i], rightMax[i]) - height[i].

Segundo, ¿puedes comprimir los arreglos de prefijos y sufijos a espacio constante? Almacenar cada máximo a la izquierda y a la derecha da una solución fácil de tiempo O(n). Los dos punteros utilizan la observación más fuerte de que el límite conocido menor ya es suficiente para finalizar un lado, una columna a la vez.

Tercero, ¿entiendes realmente la regla de movimiento? Repetir “mover el puntero más corto” no es una demostración. Una respuesta sólida establece invariantes de ciclo y maneja ambos casos: la barra actual aumenta el límite de su lado o permanece por debajo de él. Ese argumento debe mostrar por qué la región no explorada no puede cambiar la cantidad recién finalizada.

Por último, ¿puedes comparar alternativas con precisión? Los arreglos de prefijos y sufijos son los más fáciles de explicar. Una pila monotónica resuelve cuencas horizontales y se transfiere naturalmente a problemas relacionados de pilas. Dos punteros usan la menor cantidad de espacio. Las tres pueden ser correctas, pero tienen diferentes límites de espacio, estilos de demostración y extensiones.

Preguntas clarificadoras antes de responder

• ¿Cada barra tiene ancho 1? Sí. Con anchos variables, multiplica la profundidad del agua de cada columna por su ancho.
• ¿Se garantiza que las alturas sean no negativas? Sí. Las alturas negativas no tienen un significado físico definido aquí y no deben convertirse silenciosamente en fosas más profundas.
• ¿Puede estar vacío el arreglo? Las restricciones estándar indican que no. Esta implementación devuelve naturalmente 0 para un arreglo vacío, pero un contrato de API aún debería indicarlo explícitamente.
• ¿Devolvemos el total o la cantidad en cada índice? El problema principal devuelve solo el total. Una salida por índice ocupa necesariamente espacio O(n).
• ¿Se requiere espacio auxiliar constante? Sí. De lo contrario, los arreglos de prefijos y sufijos son una solución lineal más fácil de comunicar.
• ¿Puede haber desbordamiento en el tipo numérico? Calcula el límite superior a partir de las restricciones reales. Restricciones más amplias o un tipo de entero angosto requieren un acumulador más amplio.
• ¿La entrada es un perfil unidimensional o una cuadrícula bidimensional? Es unidimensional. Atrapar agua en una cuadrícula requiere una expansión de límites de afuera hacia adentro.
• ¿La implementación puede mutar la entrada? No lo necesita; el ejemplo solo lee height.

Estructura de respuesta en 30 segundos

“El agua sobre una barra es el menor entre las barras más altas a sus dos lados menos la altura de la barra. Los arreglos de prefijos y sufijos calculan todos esos máximos en tiempo lineal pero usan espacio O(n). Puedo comprimir ese estado en punteros izquierdo y derecho más leftMax y rightMax, que son las barras más altas ya exploradas desde cada lado. Cuando leftMax <= rightMax, el límite derecho conocido ya es al menos tan alto como leftMax. Si la barra izquierda actual no aumenta leftMax, su cantidad se fija en leftMax - height[left]; si aumenta el límite, su cantidad es cero. Luego avanzo el puntero izquierdo. El otro lado es simétrico. Cada índice se finaliza una vez, por lo que el tiempo es O(n) y el espacio auxiliar es O(1).”

Análisis paso a paso a profundidad

Paso 1: Definir la respuesta para una columna.

Sea:

L[i] = max(height[0..i])
R[i] = max(height[i..n-1])
water[i] = min(L[i], R[i]) - height[i]

Tanto L[i] como R[i] incluyen height[i], por lo que ninguno puede ser menor que la barra actual y la fórmula no necesita un ajuste extra a cero. El total es la suma de todos los water[i]. La fórmula también muestra por qué comprobar barras adyacentes falla: un límite más alto distante puede fijar la superficie de una cuenca completa.

Paso 2: Establecer una línea base correcta.

La solución con prefijos construye L de izquierda a derecha y R de derecha a izquierda, luego aplica la fórmula. Dos punteros no redefinen la cantidad de agua. Utilizan suficientes límites conocidos para finalizar una columna antes de almacenar cada valor de L y R.

Paso 3: Formular los invariantes de ciclo.

Al inicio de cada iteración:

1. Cada índice estrictamente a la izquierda de left ha sido finalizado según la fórmula por columna.
2. Cada índice estrictamente a la derecha de right ha sido finalizado correctamente.
3. leftMax es el máximo del rango explorado height[0..left-1], con un máximo vacío de 0.
4. rightMax es el máximo de height[right+1..n-1], usando de nuevo 0 para un rango vacío.
5. water es la suma para todos los índices finalizados.

El intervalo sin procesar es siempre [left, right]. Cada iteración debe demostrar que al menos un extremo puede finalizarse permanentemente antes de reducir este intervalo.

Paso 4: Demostrar por qué el lado con el límite conocido menor puede moverse.

Supongamos que leftMax <= rightMax y consideremos height[left]:

• Si la barra actual es más alta que leftMax, se convierte en el nuevo límite izquierdo más alto. La barra es

su propio límite izquierdo, por lo que su cantidad atrapada es 0.

• Si la barra actual no es más alta que leftMax, el verdadero máximo a su derecha es al menos el

rightMax ya observado, y rightMax >= leftMax. El límite menor queda por lo tanto fijado en leftMax, haciendo que la cantidad sea exactamente leftMax - height[left].

Ninguno de los dos casos necesita la forma exacta de la parte media sin escanear, por lo que la columna izquierda puede finalizarse. Si leftMax > rightMax, la demostración es simétrica para la columna derecha. Esta es una comparación de límites máximos conocidos, no una suposición basada en barras vecinas.

Paso 5: Implementar el algoritmo de dos punteros.

def trap(height: list[int]) -> int:
    left = 0
    right = len(height) - 1
    left_max = 0
    right_max = 0
    water = 0

    while left <= right:
        if left_max <= right_max:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1

    return water

La condición es left <= right, por lo que la última columna se finaliza cuando los punteros se encuentran. Actualizar el límite antes de sumar la diferencia hace que un nuevo máximo contribuya con cero y mantiene cada incremento no negativo. Para un arreglo vacío, right comienza en -1, el ciclo no se ejecuta y la función devuelve 0.

Paso 6: Rastrear [4, 2, 0, 3, 2, 5].

index  height  side   boundary after update  added water  total
0      4       left   leftMax=4              0            0
5      5       right  rightMax=5             0            0
1      2       left   leftMax=4              2            2
2      0       left   leftMax=4              4            6
3      3       left   leftMax=4              1            7
4      2       left   leftMax=4              2            9

La barra de altura 5 proporciona un límite derecho conocido lo suficientemente alto para cada columna izquierda restante, por lo que el algoritmo continúa finalizando el lado izquierdo. Cada columna aparece exactamente una vez, sin que ninguna cuenca se cuente dos veces.

Paso 7: Demostrar terminación, corrección y complejidad.

Inicialmente, ambos rangos procesados están vacíos, por lo que los invariantes se cumplen. El paso 4 demuestra que la columna agregada en cada iteración recibe exactamente su cantidad por columna. Actualizar leftMax o rightMax preserva su definición para la siguiente iteración. Cada iteración incrementa left o decrementa right; tras un número finito de pasos, left > right. En ese punto, cada índice ha sido finalizado correctamente, por lo que la suma es correcta.

Cada índice se visita una vez, lo que da un tiempo de O(n). El algoritmo no asigna almacenamiento proporcional al tamaño de entrada más allá del resultado escalar sin arreglos de salida; dos punteros, dos límites y un acumulador usan espacio auxiliar de O(1).

Paso 8: Verificar contra un oráculo de fórmula y casos adversos.

Las pruebas fijas deben incluir una barra, dos barras, todos ceros, entradas estrictamente crecientes y decrecientes, todas las alturas iguales, varias cuencas separadas, una cuenca de fondo plano, los ejemplos estándar y [3, 0, 3]. Este último caso expone una implementación que usa incorrectamente left < right y omite el índice de encuentro.

Para arreglos no negativos aleatorios cortos, construye L y R, usa la fórmula por columna como un oráculo y compárala con el resultado de dos punteros. También verifica que el resultado sea no negativo, que invertir el arreglo conserve el total y que agregar una barra de altura cero en cualquiera de los extremos exteriores no cambie el total original. Las pruebas diferenciales encuentran errores de implementación; la demostración por invariantes sigue siendo el argumento de corrección.

Respuesta de ejemplo sólida

“Primero reduzco el problema a una fórmula por índice. La profundidad en i es min(max(height[0..i]), max(height[i..n-1])) - height[i]. Dos arreglos de prefijos implementan esa fórmula en tiempo O(n) y espacio O(n). Para lograr espacio auxiliar constante, uso dos punteros.

Dentro del ciclo, leftMax y rightMax son las barras más altas ya exploradas fuera de los dos punteros. Si leftMax <= rightMax, finalizo el puntero izquierdo. Si su barra actual incrementa leftMax, su cantidad es cero. De lo contrario, el rightMax conocido ya es al menos tan alto como el límite izquierdo, por lo que la parte media desconocida no puede reducir el límite menor por debajo de leftMax; la cantidad queda fija en leftMax - height[left]. Luego muevo el puntero izquierdo hacia adentro. El lado derecho es simétrico.

Cada iteración procesa permanentemente una columna, por lo que todas las columnas quedan listas al terminar. El tiempo es O(n), y los punteros, los límites y el acumulador usan espacio auxiliar de O(1). Probaría con entradas cortas, arreglos monótonos y de elementos iguales, múltiples cuencas y [3, 0, 3], y luego compararía diferencialmente casos aleatorios cortos con la fórmula de arreglos de prefijos.”

Errores comunes

• Restar del mayor de los dos máximos → El agua se derrama sobre el límite más bajo → Usa siempre el máximo menor.
• Revisar solo barras adyacentes → Se ignora un límite distante → Comienza a partir de la fórmula completa izquierda/derecha por columna.
• Sumar antes de actualizar el límite actual → Un nuevo máximo puede producir una cantidad negativa → Actualiza primero, luego suma una diferencia no negativa.
• Usar left < right → El punto medio de [3, 0, 3] puede quedar sin procesar → Incluye la posición de encuentro en el ciclo.
• Mover el lado del límite mayor sin una demostración → El lado opuesto desconocido aún puede determinar la superficie más baja → Finaliza solo el lado respaldado por un límite opuesto conocido.
• Aplicar la fórmula de Container With Most Water → width × boundary height cuenta dos veces barras y columnas → Suma la profundidad del agua sobre cada barra.
• Detener el análisis en el trabajo constante por iteración → No explica por qué las barras futuras no pueden cambiar la respuesta → Establece los invariantes de límites y la demostración de dos casos.
• Afirmar que una pila monótona también usa espacio O(1) → Una entrada monótona puede retener n índices → Reporta espacio en el peor de los casos de O(n).
• Probar solo el ejemplo ilustrado → Los límites de encuentro, monótonos y de igual altura quedan sin verificar → Agrega casos fijos y un oráculo con arreglos de prefijos.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Por qué no comparar height[left] y height[right] directamente?

Otra formulación correcta compara las alturas de los puntos extremos actuales, pero necesita un invariante y un orden de actualización correspondientes. Esta implementación compara leftMax y rightMax porque esos valores se asignan directamente a la fórmula de límites por columna. No combines la condición de una formulación con la demostración de la otra; elige una y mantén el código, la explicación y la demostración coherentes.

Pregunta de seguimiento 2: ¿Qué pasa si la función debe devolver el agua sobre cada barra?

Escribe cada incremento finalizado en un arreglo de longitud n, y luego súmalo o acumula el total al mismo tiempo. El tiempo de ejecución sigue siendo O(n), mientras que la salida en sí requiere espacio de O(n). Si un llamador consume los resultados como un flujo (stream), ten en cuenta que dos punteros no finalizan los índices en orden de izquierda a derecha; incluye el índice o reordena la salida completa.

Pregunta de seguimiento 3: ¿Qué pasa si las alturas llegan solo como un flujo de izquierda a derecha?

Una respuesta exacta depende de un límite derecho futuro, por lo que no todas las columnas pueden finalizarse de inmediato con memoria fija. Una pila monótona puede retener cuencas abiertas y resolverlas cuando llega un límite derecho lo suficientemente alto, pero su memoria en el peor de los casos sigue siendo O(n). Un límite estricto de memoria requiere una aproximación, almacenamiento externo o una segunda pasada; no puede preservar la promesa original de espacio constante exacto.

Pregunta de seguimiento 4: ¿Qué pasa si las barras tienen diferentes anchos?

Si la barra i abarca independientemente width[i], la lógica de altura de límites se mantiene igual y su volumen es waterDepth[i] * width[i]. Si en cambio la entrada proporciona coordenadas irregulares y espacios vacíos, primero define la altura sobre cada intervalo horizontal. La distancia entre centros de barras vecinas no es automáticamente el ancho de una barra completa.

Pregunta de seguimiento 5: ¿Cómo se atrapa agua en un mapa de alturas bidimensional?

Una celda de la cuadrícula está limitada por todo el límite exterior, por lo que dos punteros direccionales no son suficientes. Un algoritmo común inserta todas las celdas de los bordes en un min-heap y se expande repetidamente hacia adentro desde el límite actual más bajo. Un vecino no visitado más bajo aporta la diferencia de altura, y el mayor entre el límite y el vecino se convierte en el límite efectivo para expansiones posteriores. Con un conjunto de visitados, una cuadrícula de m × n toma un tiempo de O(mn log(mn)) y un espacio de O(mn).

Pregunta de seguimiento 6: ¿Cuándo es preferible la solución con pila monótona?

La pila es natural cuando una pregunta de seguimiento pide cada cuenca cerrada por límites izquierdo y derecho, una explicación del ancho horizontal, o una transición a problemas de pilas monótonas tipo histograma. Almacena índices en orden decreciente de altura. Una barra más alta extrae (pop) el fondo de una cuenca; el nuevo tope de la pila y la barra actual forman sus límites, y el algoritmo suma effective width × new water-layer depth. El tiempo total sigue siendo O(n), con un espacio auxiliar en el peor de los casos de O(n).