Implementación de Trapping Rainwater en Complejidad Lineal

Si ya dominaste el problema de Container with most water, es momento de dar un paso más con una variación que eleva la dificultad de forma progresiva. Se trata del reto Trapping rainwater, un clásico en entrevistas técnicas y competencias de programación que pone a prueba tu capacidad para pensar en soluciones eficientes.

¿En qué consiste el reto Trapping rainwater?

El planteamiento es similar al ejercicio anterior: se recibe una lista de números que representan alturas de barras en un tablero. Sin embargo, la diferencia clave es que ahora no se busca el contenedor con más agua entre dos barras, sino calcular cuánta agua puede atrapar todo el tablero en conjunto [0:22].

Imagina un perfil de terreno con elevaciones y valles. Cuando llueve, el agua se acumula en los espacios entre las barras más altas. El objetivo es determinar la cantidad total de agua atrapada entre todas las barras.

¿Por qué la complejidad temporal O(n) es importante?

El reto tiene una condición fundamental: la solución debe implementarse con complejidad temporal lineal, es decir, O(n) [0:18]. Esto significa que el algoritmo debe recorrer los datos en una sola pasada o en un número fijo de pasadas, sin bucles anidados que incrementen el tiempo de ejecución.

Algunas estrategias comunes para lograrlo:

• Utilizar dos punteros que se muevan desde los extremos hacia el centro.
• Precalcular las alturas máximas por la izquierda y por la derecha en arreglos auxiliares.
• Mantener un registro del máximo acumulado para determinar cuánta agua cabe en cada posición.

¿Cómo se calcula el agua en cada posición?

Para cada barra, el agua que puede almacenar depende de la altura mínima entre el máximo a su izquierda y el máximo a su derecha, menos la altura de la barra misma. Si ese valor es positivo, se suma al total. Si es negativo o cero, esa posición no atrapa agua.

¿Qué enfoque usar para resolver en O(n)?

La técnica de dos punteros es especialmente elegante para este problema. Se colocan un puntero al inicio y otro al final del arreglo. En cada iteración se avanza el puntero del lado con menor altura máxima, calculando el agua atrapada en esa posición. De esta forma se resuelve en una sola pasada sin estructuras adicionales costosas.

Otra opción válida es usar dos arreglos auxiliares: uno que almacene el máximo desde la izquierda y otro desde la derecha. Con esos datos, una tercera pasada permite sumar el agua total. Aunque usa más memoria, sigue siendo O(n) en tiempo.

¿Cómo practicar y compartir tu solución?

Este tipo de retos fortalece habilidades fundamentales como el pensamiento algorítmico, la optimización de complejidad y el manejo de estructuras de datos lineales. Anímate a implementar tu solución, probarla con distintos casos y compartirla en los comentarios junto con tus dudas o la experiencia que tuviste al resolverlo [0:32].