Sesión 50: Trapping Rain Water (CTCI 17.21 / LeetCode 42 Hard) — Two Pointers vs Monotonic Stack#

Navegación rápida:

• ← Sesión 49: Cierre Magistral y Consolidación de la Semana 7
• Sesión 51: Monotonic Deque & Sliding Window Maximum (LeetCode 239) →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 65-80 minutos.
• Código fuente compilado y probado: practica-rust/dia_50.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

En esta sesión inauguramos la Semana 8: Patrones Avanzados y Estructuras de Datos de Élite. Abordamos uno de los problemas canónicos más célebres de entrevistas técnicas para roles Senior y Staff: el cálculo de volumen de agua atrapada en histogramas. Consulta el Glosario Maestro y la Guía de Diagramas.

Trapping Rain Water (Volumen de Agua Atrapada / CTCI 17.21 & LC 42)#

• (a) En palabras simples (intuición): Imagina que construyes un relieve con bloques de construcción de distintas alturas y dejas caer una lluvia torrencial. El agua se acumulará en los huecos o valles entre las torres altas, pero si una torre es baja en los extremos, el agua se desbordará y caerá al suelo. Quieres calcular cuántos litros de agua quedan retenidos en total sobre el relieve.
• (b) Definición técnica paso a paso: Dado un arreglo de enteros no negativos height, donde cada barra tiene ancho 1, calcular el volumen total de agua retenida. Para cada columna i, el agua contenida está acotada verticalmente por el principio de vasos comunicantes:

Donde left_max[i] es la barra más alta en [0..i] y right_max[i] es la barra más alta en [i..N-1].

• (c) Cómo funciona en Rust (memoria y tipos): La solución óptima no reserva memoria Heap (O(1) espacio auxiliar) operando sobre un slice &[u32].
• (d) Error típico de Junior: Intentar simular el llenado de agua gota por gota o nivel por nivel horizontal con bucles anidados en tiempo O(N · max(H)), lo cual genera TLE.

Enfoque de Dos Punteros Convergentes (O(N) Tiempo, O(1) Espacio)#

• (a) En palabras simples (intuición): Colocas dos exploradores: uno en el extremo izquierdo y otro en el extremo derecho del terreno. El explorador que esté parado frente a la pared más baja es el que camina hacia el centro. ¿Por qué? Porque el explorador sabe que en el otro lado del mapa hay una montaña más alta que la suya, lo que garantiza que cualquier agua que mida frente a su pared jamás se desbordará por el otro extremo.
• (b) Definición técnica paso a paso: Optimización que elimina la necesidad de precomputar los arreglos de prefijo y sufijo. Se mantienen dos punteros left = 0, right = n - 1 y dos acumuladores de máximos left_max y right_max:
• Si height[left] ≤ height[right]: Se garantiza que existe una barrera a la derecha ≥ height[left]. Por tanto, el cuello de botella de la columna left está gobernado exclusivamente por left_max. Calculamos water += left_max - height[left] y avanzamos left += 1.
• Si no, el cuello de botella de la columna right está gobernado por right_max. Calculamos agua y decrementamos right -= 1.
• (c) Cómo funciona en Rust (memoria y tipos): Se ejecuta en registros de CPU sin una sola asignación en memoria dinámica.
• (d) Error típico de Junior: Avanzar el puntero del lado con la pared más alta; si avanzas el lado alto, pierdes la garantía de que el lado opuesto contiene un muro de contención suficiente.

Enfoque de Pila Monótona (Cálculo Horizontal por Capas)#

• (a) En palabras simples (intuición): En lugar de calcular el agua columna por columna hacia arriba (como tubos de ensayo), calculas el agua llenando piscinas horizontales por capas. Cada vez que el suelo desciende, guardas el escalón en una pila. Cuando el terreno vuelve a subir de golpe, acabas de encontrar la pared derecha de una piscina: mides el fondo, mides la pared izquierda que tenías guardada y sumas el agua de esa capa horizontal.
• (b) Definición técnica paso a paso: Mantenimiento de una pila de índices con alturas monótonamente decrecientes. Al encontrar una barra current con height[current] > height[stack.top()], se detecta un valle:

1. Se extrae el fondo: bottom = stack.pop().
2. Si la pila queda vacía, no hay pared izquierda que contenga agua.
3. Si hay pared izquierda left = stack.top(), el ancho es distance = current - left - 1, y la altura de la capa es bounded_h = min(height[left], height[current]) - height[bottom].
4. Se acumula distance × bounded_h.

• (c) Cómo funciona en Rust (memoria y tipos): Usa stack: Vec<usize> en el Heap. Cada índice se apila y desapila como máximo una vez (O(N) amortizado).
• (d) Error típico de Junior: Olvidar restar height[bottom] al calcular la altura acotada, lo que contaría dos veces el volumen de capas de agua inferiores.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Prueba Matemática de Dos Punteros: ¿Por qué no Importa el Lado Contrario?#

La duda más común de cualquier desarrollador Trainee es: "Si estoy en left y solo conozco left_max y height[right], ¿cómo sé que más adelante a la derecha no hay una pared más baja que deje escapar el agua?"

Veamos la deducción formal:

1. Supongamos que en la iteración actual se cumple la condición:
   height[left] ≤ height[right]
2. Por definición de right_max, sabemos que right_max ≥ height[right].
3. Por transitividad matemática:
   left_max ≤ height[left] ≤ height[right] ≤ right_max ⟹ left_max ≤ right_max
4. La fórmula universal del agua en la columna left es:
   water[left] = min(left_max, ;right_max) - height[left]
5. Como acabamos de demostrar que left_max ≤ right_max, el mínimo entre ambos es indiscutiblemente left_max:
   min(left_max, ;right_max) = left_max
6. Conclusión: El valor exacto de las barras intermedias entre left y right es completamente irrelevante. Sabemos con certeza matemática que en el lado derecho existe al menos una pared con altura ≥ left_max que retendrá el agua. El cálculo es exacto y libre de especulación.

Vertical (Columnas) vs Horizontal (Capas de Stack): Comparativa Anatómica#

Terreno: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

ENFOQUE VERTICAL (Two Pointers / Prefix Arrays):
Suma el agua sumando columnas verticales completas:
               █
       █ ~ ~ ~ █ █ ~ █
   █ ~ █ █ ~ █ █ █ █ █ █
Col:0 1 2 3 4 5 6 7 8 9 10 11
Agua: 0 0 1 0 1 2 1 0 0 1 0  0  -> Total: 6

ENFOQUE HORIZONTAL (Monotonic Stack):
Suma el agua por rectángulos horizontales al resolver valles:
Capa 2:        ~ ~ ~ ~ ~        (altura 1, ancho entre col 3 y 7)
Capa 1:    ~   ~ ~ ~ ~ ~   ~    (rectángulos de nivel bajo)
Ambos enfoques suman exactamente el mismo volumen total: 6 unidades.

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama de Decisión de Dos Punteros#

Consulta el diagrama vectorial:

flowchart TD
    START["Inicio: left = 0, right = n - 1, left_max = 0, right_max = 0"] --> COND{"left < right"}
    COND -->|No| DONE["Fin: Retornar total_water"]
    COND -->|Sí| CMP{"¿height[left] <= height[right]?"}
    CMP -->|Sí: Cuello de botella en Izquierda| L_CHECK{"¿height[left] >= left_max?"}
    L_CHECK -->|Sí| L_UPDATE["left_max = height[left]"]
    L_CHECK -->|No| L_ADD["total_water += left_max - height[left]"]
    L_UPDATE --> L_INC["left += 1"]
    L_ADD --> L_INC
    L_INC --> COND
    CMP -->|No: Cuello de botella en Derecha| R_CHECK{"¿height[right] >= right_max?"}
    R_CHECK -->|Sí| R_UPDATE["right_max = height[right]"]
    R_CHECK -->|No| R_ADD["total_water += right_max - height[right]"]
    R_UPDATE --> R_DEC["right -= 1"]
    R_ADD --> R_DEC
    R_DEC --> COND

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Ejecución de trap_rain_water_two_pointers(&[4, 2, 0, 3, 2, 5]):

STACK:
left = 0, right = 5, left_max = 0, right_max = 0, total_water = 0
Slice height en memoria: [ 4, 2, 0, 3, 2, 5 ]

ITERACIÓN 1:
height[0] (4) <= height[5] (5) -> procesa izquierda.
height[0] (4) >= left_max (0) -> left_max = 4.
left = 1. total_water = 0.

ITERACIÓN 2:
height[1] (2) <= height[5] (5) -> procesa izquierda.
height[1] (2) < left_max (4) -> total_water += 4 - 2 = 2.
left = 2. total_water = 2.

ITERACIÓN 3:
height[2] (0) <= height[5] (5) -> procesa izquierda.
height[2] (0) < left_max (4) -> total_water += 4 - 0 = 4.
left = 3. total_water = 6.

ITERACIÓN 4:
height[3] (3) <= height[5] (5) -> procesa izquierda.
height[3] (3) < left_max (4) -> total_water += 4 - 3 = 1.
left = 4. total_water = 7.

ITERACIÓN 5:
height[4] (2) <= height[5] (5) -> procesa izquierda.
height[4] (2) < left_max (4) -> total_water += 4 - 2 = 2.
left = 5. total_water = 9.

TERMINACIÓN: left == right (5 == 5). Bucle finaliza.
Retorno: total_water = 9.
Memoria auxiliar asignada en Heap: 0 bytes.

4. Las 3 Trampas Clásicas en Entrevistas y Cómo Evitarlas#

Trampa 1: Olvidar Validar Longitudes Menores a 3#

• El error: Ejecutar el algoritmo sin comprobar si height.len() < 3.
• Por qué falla: Físicamente se requieren al menos dos paredes y un espacio intermedio (mínimo 3 barras) para retener agua. Arreglos de tamaño 0, 1 o 2 jamás pueden atrapar agua. Además, para arreglos vacíos right = n - 1 causaría un pánico en Rust por subdesbordamiento de usize.
• La solución: Caso base inmediato en la primera línea:

  if height.len() < 3 { return 0; }

Trampa 2: Desbordar Índices en Monotonic Stack al Vaciar la Pila#

• El error: Escribir let left = stack.pop().unwrap() sin verificar si la pila quedó vacía tras extraer el fondo del valle.
• Por qué falla: Si extraes el fondo del pozo y la pila queda vacía, significa que no existe ninguna pared a la izquierda que pueda contener agua; el agua se derrama hacia la izquierda.
• La solución: Comprobar if stack.is_empty() { break; } antes de calcular el agua de la capa.

Trampa 3: Usar Tipos con Signo y Comparaciones Negativas#

• El error: Usar enteros con signo e ignorar que si una barra es más alta que el máximo previo, la resta max - height[i] puede dar valores negativos.
• Por qué falla: Si restas un número grande de uno pequeño sin comprobar el máximo, sumarías agua negativa destruyendo el total acumulado.
• La solución: Actualizar primero el máximo condicionalmente antes de restar:

  if height[left] >= left_max {
      left_max = height[left];
  } else {
      total_water += left_max - height[left];
  }

5. Implementación Canónica en Rust y Comparativa con Python#

Implementación en Rust (practica-rust/dia_50.rs)#

/// Enfoque 3: Dos Punteros Convergentes Óptimo O(1) Espacio.
pub fn trap_rain_water_two_pointers(height: &[u32]) -> u32 {
    let n = height.len();
    if n < 3 {
        return 0;
    }

    let mut left = 0usize;
    let mut right = n - 1;
    let mut left_max = 0u32;
    let mut right_max = 0u32;
    let mut total_water = 0u32;

    while left < right {
        if height[left] <= height[right] {
            if height[left] >= left_max {
                left_max = height[left];
            } else {
                total_water += left_max - height[left];
            }
            left += 1;
        } else {
            if height[right] >= right_max {
                right_max = height[right];
            } else {
                total_water += right_max - height[right];
            }
            right -= 1;
        }
    }

    total_water
}

/// Enfoque 2: Pila Monótona Decreciente (Capas Horizontales).
pub fn trap_rain_water_monotonic_stack(height: &[u32]) -> u32 {
    let n = height.len();
    if n < 3 {
        return 0;
    }

    let mut stack: Vec<usize> = Vec::new();
    let mut total_water = 0;

    for current in 0..n {
        while let Some(&top_idx) = stack.last() {
            if height[current] > height[top_idx] {
                stack.pop();
                if let Some(&left_idx) = stack.last() {
                    let distance = (current - left_idx - 1) as u32;
                    let bounded_height = height[left_idx].min(height[current]) - height[top_idx];
                    total_water += distance * bounded_height;
                }
            } else {
                break;
            }
        }
        stack.push(current);
    }

    total_water
}

Implementación de Referencia en Python (practica/dia_50_trapping_rain_water.py)#

from typing import List


def trap_rain_water_two_pointers(height: List[int]) -> int:
    """Enfoque 3: Dos Punteros O(N) tiempo, O(1) espacio."""
    if not height or len(height) < 3:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    total_water = 0

    while left < right:
        if height[left] <= height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                total_water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                total_water += right_max - height[right]
            right -= 1

    return total_water

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Ejercicios de Práctica Independiente y Casos Límite#

1. Paso Límite 1: Terreno Estrictamente Creciente o Decreciente: - Para height = [1, 2, 3, 4, 5] o height = [5, 4, 3, 2, 1], verifica que el retorno sea estrictamente 0 (no hay valles).
2. Paso Límite 2: Cañón Profundo con Paredes Gigantes: - Para height = [1000, 0, 1000], comprueba que el agua calculada sea exactamente 1000.
3. Paso Límite 3: Contenedor con Más Agua (LeetCode 11 vs 42): - Compara las diferencias matemáticas entre Container With Most Water (donde solo importan las dos paredes exteriores elegidas) y Trapping Rain Water (donde todas las barras interiores absorben o restan volumen de agua).

Navegación final:

• ← Sesión 49: Cierre Magistral y Consolidación de la Semana 7
• Sesión 51: Monotonic Deque & Sliding Window Maximum (LeetCode 239) →
• Glosario Maestro
• Guía de Diagramas de Arquitectura