Implementación de Trapping Rainwater en Complejidad Lineal

Clase 16 de 35 • Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

Resumen

¿Qué es el desafío Trapping Rainwater?

El desafío conocido como "Trapping Rainwater" es una versión más compleja del problema anterior "Container with Most Water". Este tipo de problemas son populares en el campo de las entrevistas técnicas, ya que desafían las habilidades de pensamiento lógico y programación eficiente del candidato. La tarea principal aquí es calcular cuánta agua puede ser atrapada después de una lluvia, dado un arreglo de números que representan diferentes alturas.

¿Cómo podemos resolver este problema?

La clave para resolver el problema de "Trapping Rainwater" es lograr implementar una solución que tenga una complejidad temporal lineal, es decir, O(N). Aquí te presentamos una guía para abordar este problema:

Comprender el Problema: Imagina una serie de columnas verticales, cada una con una altura específica, que representan el perfil de un gráfico de barras. Entre estas columnas, cuando llueve, se puede acumular agua.
Identificar Necesidades: Necesitas determinar cuánta agua puede atraparse entre las columnas en diferentes escenarios.
Algoritmo Eficiente:
- Dos punteros: Comienza colocando dos punteros en ambas extremidades del arreglo.
- Condiciones de Borde: Recorre el arreglo moviendo los punteros hacia el centro.
- Calcular Volumen de Agua: Mide la cantidad de agua que cada posición puede acumular basándote en las alturas máximas encontradas a cada lado.
Implementación en Tiempo Lineal:
- Mantén un seguimiento de las alturas máximas desde la izquierda y desde la derecha.
- Calcula y suma el agua atrapada en cada posición a medida que avanzas sobre el arreglo desde ambos lados simultáneamente.

Recomendaciones para abordar el desafío

Analiza Casos de Borde: Asegúrate de incluir casos de borde en tus consideraciones, tales como cuando todas las alturas son iguales o cuando el arreglo contiene solo una barra única.
Optimización: Piensa en la forma de optimizar espacio. Mientras la complejidad temporal es prioritaria, un uso eficiente del espacio también puede ser un factor determinante en entrevistas.
Itera y Mejora: No te desanimes si no obtienes la solución de inmediato. Utiliza las revisiones para identificar ajustes y combatir errores lógicos.
Comunidad y Feedback: Usa las plataformas de estudio, como los comentarios en los cursos, para compartir tus soluciones y recibir feedback constructivo.

¡Anímate a resolver este reto y aplica tus conocimientos! Las habilidades que adquieres resolviendo problemas como este te preparan para enfrentar desafíos reales en el mundo de la programación y el desarrollo de software.

Juan Pablo Carrasco Venegas

student•

Pasé días pensando en la solución, pensé que la tenía péro no tuve en cuenta los espacios ocupados de las columnas -- me rendí y me documenté un poco en leetCode y llegué a este código en C# que pasó las pruebas

    private int getTrappedWater(List<int> heights)
    {
        int p1 = 0;
        int p2 = heights.Count-1;
        int trappedWater = 0;
        int maxLHeight = 0;
        int maxRHeight = 0;
        while (p1<p2)
        {
            if (heights[p1] < heights[p2])
            {
                if (heights[p1] < maxLHeight)
                {
                    trappedWater += maxLHeight - heights[p1];
                } else
                {
                    maxLHeight = heights[p1];
                }
                p1++;
            } else
            {
                if (heights[p2] < maxRHeight)
                {
                    trappedWater += maxRHeight - heights[p2];
                } else
                {
                    maxRHeight = heights[p2];
                }
                p2--;
            }
        }
        return trappedWater;
    }

y en javascript

function trappedWater(listOfColumns){
    let p1 = 0;
    let p2 = listOfColumns.length-1; //10
    let trappedWater = 0;
    let maxLHeight = 0;
    let maxRHeight = 0;
    while (p1<p2) {
        if (listOfColumns[p1] < listOfColumns[p2]) {
            if (listOfColumns[p1] < maxLHeight) {
                trappedWater += maxLHeight-listOfColumns[p1];
            } else{
                maxLHeight = listOfColumns[p1];
            }
            p1++;
        }else{
            if (listOfColumns[p2] < maxRHeight) {
                trappedWater += maxRHeight - listOfColumns[p2];
            }   else{
                maxRHeight = listOfColumns[p2];
            }
            p2--;
        }
        console.log(`p1: ${p1}, p2:${p2}`);
        console.log(`trappedWater: ${trappedWater}, maxLHeight: ${maxLHeight}, maxRHeight: ${maxRHeight}`);
    }
    return trappedWater;
}

Nicolas Alpargatero

student•

Me dio embarrada que no logre encontrar para el Big O(n) pero usando tus guías comprendí mejor gracias.

Tomas Pucutay

student•

Una de las soluciones en Python La existencia de las variables maxIzq y maxDer sirven para establecer el nivel del agua, de modo que la resta con una altura menor indique que se está almacenando agua

def trappingRainWater(alturas):
    izq = 0
    der = len(alturas)-1 
    maxIzq = maxDer = 0
    aguaRecolectada = 0

    while(izq <= der):
        if(alturas[izq]<=alturas[der]): 
            if(alturas[izq]>=maxIzq): maxIzq = alturas[izq]
            else: aguaRecolectada += maxIzq - alturas[izq]
            izq += 1
        else:
            if(alturas[der]>=maxDer): maxDer = alturas[der]
            else: aguaRecolectada += maxDer - alturas[der]
            der -= 1
    return aguaRecolectada

Misael Mondragón Lenis

student•

Tambien veo la relación de los pointers izq y der, cuando evaluamos las alturas y comparamos nos esta indicando en que lado es mas **probable **que acumule agua (primer if).

Por ejemplo si la altura en el pointer izq es 6 y en el pointer der es 4 es mas probable que el lado derecho vaya a acumular agua entonces te vas a evaluar si hay acumulación por ese lado.

Tomas Pucutay

student•

Es una buena apreciación; sin embargo, va más hacia la lógica per se. En tu caso hipotético, si la columna izquierda es 6, y la derecha es 4. En el caso que hubiera colocado la lógica al revés la evaluación comenzaría y continuaría con izq = 6, y eventualmente al mover el apuntador llegaría al error. . Porque en algún punto llegaría a que el apuntador izquierdo es 1 menos que el apuntador derecho. Y en ese caso al evaluar la altura del apuntador izquierdo sumaría erroneamente (6-[su altura correspondiente]) y eso sería inválido porque estaría frente a la columna de 4, es decir que no acumula

Christopher Andrés Guano Valencia

student•

👨‍💻 Solución en JavaScript / TypeScript

Complejidad Temporal: O(n) Complejidad Espacial: O(1) .

function trap(height: number[]): number {
  let len = height.length - 1
  let [maxLeft, maxRight] = [height[0], height[len]]
  let [left, right] = [0, len]
  let waterTrap = 0

  while (left < right) {
    if (maxLeft < maxRight) {
      left++
      maxLeft = Math.max(maxLeft, height[left])
      waterTrap += maxLeft - height[left]
    } else {
      right--
      maxRight = Math.max(maxRight, height[right])
      waterTrap += maxRight - height[right]
    }
  }

  return waterTrap
}

José Ramón García

student•

Yo lo resolví así.

Tomamos dos punteros como en el problema anterior, y con base en las alturas de esas dos columnas, marcamos un límite, es decir, debajo de ese límite sí o sí debe de haber agua.

Después movemos el puntero que tenga la menor altura (sea p2) hasta encontrar una que sea mayor al puntero p1,mientras hacemos esto al mismo tiempo vamos calculando el área del agua que en este caso será igual a limite-altura_columna_actual si y solo si la altura de la columna actual es mayor que el límete, cuando obtengamos eso vamos a poner un nuevo límite, y así hasta que los punteros estén uno del lado del otro.

def trapping_water(alturas):
    L = len(alturas)
    p1 = 0
    p2 = L-1
    area_agua = 0
    altura_limite = 0
    alt_izq_old = 0
    alt_der_old = 0

    while p1 < p2-1:
        alt_izq_new = alturas[p1]
        alt_der_new = alturas[p2]
        min_1 = min(alt_izq_old,alt_der_old)
        min_2 = min(alt_izq_new,alt_der_new)

        if min_2 >= min_1:
            altura_limite = min_2
            alt_der_old = alt_der_new
            alt_izq_old = alt_izq_new

        if alt_der_new < alt_izq_new:
            p2 -=1
            alt_der_new = alturas[p2]

            if alt_der_new < altura_limite:
                area_agua += altura_limite - alt_der_new

        else:
            p1 +=1 
            alt_izq_new = alturas[p1]
            if alt_izq_new < altura_limite:
                area_agua += altura_limite - alt_izq_new
            
    return area_agua
```Aquí algunos ejemplos:

![](https://static.platzi.com/media/user_upload/250311_16h05m52s_screenshot-aa7fc73a-03bc-45f9-a054-7ecd17433781.jpg)

David Higuera

student•

function trapWater(columnList) {
	// pointers
	let left = 0,
		right = columnList.length - 1;

	// max high record
	let leftMax = 0,
		rightMax = 0;

	// accumulation
	let water = 0;

	// iterate the list from both edges to center
	while (left < right) {
		// determine which side the smallest
		if (columnList[left] < columnList[right]) {
			// is this Right Left
			if (columnList[left] >= leftMax) {
				// set new Left Max
				leftMax = columnList[left];
			} else {
				// add water content
				water += leftMax - columnList[left];
			}
			// move left pointer
			left++;
		} else {
			// is this Right Max
			if (columnList[right] >= rightMax) {
				// set new Right Max
				rightMax = columnList[right];
			} else {
				// add water content
				water += rightMax - columnList[right];
			}
			// move right pointer
			right--;
		}
	}

	// total accumulated
	return total;
}

Carlos Hernandez

student•

Mi solución: const getTrappedRainWater = (heights) => { let trappedWater = 0; let leftPointer = 0; let rightPointer = 2; while (leftPointer < heights.length - 2) { const leftHeight = heights[leftPointer]; const rightHeight = heights[rightPointer]; // Calculate storaged water if (rightHeight >= leftHeight) { // Water is equals to total storaged water minus obstacles const totalWater = (rightPointer - leftPointer - 1) * (Math.min(leftHeight, rightHeight)); const obstacles = heights.filter((_, i) => i < rightPointer && i > leftPointer); if (!obstacles.find((obstacle) => obstacle > leftHeight)) { const difference = totalWater - obstacles.reduce((current, obstacle) => current + obstacle, 0); trappedWater += difference; leftPointer = rightPointer; rightPointer = rightPointer + 2; continue; } rightPointer++; } if (rightHeight < leftHeight) { rightPointer++; } if (rightPointer > heights.length - 1) { leftPointer++; rightPointer = leftPointer + 2; } } return trappedWater;} console.log(getTrappedRainWater([0,1,0,2,1,0,1,3,2,1,2,1])); //6

const getTrappedRainWater = (heights) => {
    let trappedWater = 0;

    let leftPointer = 0;
    let rightPointer = 2;
    while (leftPointer < heights.length - 2) {
        const leftHeight = heights[leftPointer];
        const rightHeight = heights[rightPointer];

        // Calculate storaged water
        if (rightHeight >= leftHeight) {
            // Water is equals to total storaged water minus obstacles
            const totalWater = (rightPointer - leftPointer - 1) * (Math.min(leftHeight, rightHeight));

            const obstacles = heights.filter((_, i) => i < rightPointer && i > leftPointer);

            if (!obstacles.find((obstacle) => obstacle > leftHeight)) {
                const difference = totalWater - obstacles.reduce((current, obstacle) => current + obstacle, 0);
                trappedWater += difference;

                leftPointer = rightPointer;
                rightPointer = rightPointer + 2;
                continue;
            }
            rightPointer++;
        }
        
        if (rightHeight < leftHeight) {
            rightPointer++;
        }

        if (rightPointer > heights.length - 1) {
            leftPointer++;
            rightPointer = leftPointer + 2;
        }
    }

    return trappedWater;
}

console.log(getTrappedRainWater([0,1,0,2,1,0,1,3,2,1,2,1])); //6

Carlos Hernandez

student•

Otra solución optimizando el cálculo de obstáculos en los contenedores:const getTrappedRainWater = (heights) => { let trappedWater = 0; let leftPointer = 0; let rightPointer = 1; let obstacleCounter = 0; while (leftPointer < heights.length - 2) { const leftHeight = heights[leftPointer]; const rightHeight = heights[rightPointer]; // Calculate storaged water if (rightHeight >= leftHeight) { // Water is equals to total storaged water minus obstacles const totalWater = (rightPointer - leftPointer - 1) * (Math.min(leftHeight, rightHeight)); const difference = totalWater - obstacleCounter; trappedWater += difference; leftPointer = rightPointer; rightPointer = rightPointer + 1; obstacleCounter = 0; continue; } if (rightHeight < leftHeight) { rightPointer++; if (rightHeight > 0) obstacleCounter += rightHeight; } if (rightPointer > heights.length - 1) { leftPointer++; rightPointer = leftPointer + 1; obstacleCounter = 0; } } return trappedWater;} console.log(getTrappedRainWater([0,1,0,2,1,0,1,3,2,1,2,1])); //6```js const getTrappedRainWater = (heights) => { let trappedWater = 0;

let leftPointer = 0;
let rightPointer = 1;
let obstacleCounter = 0;

while (leftPointer < heights.length - 2) {
    const leftHeight = heights[leftPointer];
    const rightHeight = heights[rightPointer];

    // Calculate storaged water
    if (rightHeight >= leftHeight) {
        // Water is equals to total storaged water minus obstacles
        const totalWater = (rightPointer - leftPointer - 1) * (Math.min(leftHeight, rightHeight));

        const difference = totalWater - obstacleCounter;
        trappedWater += difference;

        leftPointer = rightPointer;
        rightPointer = rightPointer + 1;
        obstacleCounter = 0;
        continue;
    }
    
    if (rightHeight < leftHeight) {
        rightPointer++;
        if (rightHeight > 0) obstacleCounter += rightHeight;
    }

    if (rightPointer > heights.length - 1) {
        leftPointer++;
        rightPointer = leftPointer + 1;
        obstacleCounter = 0;
    }
}

return trappedWater;

}

console.log(getTrappedRainWater([0,1,0,2,1,0,1,3,2,1,2,1])); //6

Giovanni Osorio

student•

Solución O(n) Python

def water_trapped(columns: list[int]) -> int:
    i = 0
    j = i + 2
    water_acc = 0
    acc = 0
    water = 0
    while j < len(columns):
        col1 = columns[i]
        col2 = columns[j]
        print(col1, col2)
        if col1 == 0:
            i += 1
            j = i + 2
        elif col1 > col2:
            water = min(col1,col2) * (j-i-1) - sum(columns[i+1:j])
            if water > 0:
                acc += water  #### accumulative until col1 moves to a bigger column
            j += 1
        else: ### col2 >= col1
            water = min(col1,col2) * (j-i-1) - sum(columns[i+1:j]) - acc
            acc = 0
            i = j
            j = i + 2
        
        if water > 0:
            water_acc += water
        
        print('water', water)
        print('water_acc', water_acc)
    
    return water_acc
```def water\_trapped(*columns*: list\[int]) -> int:    i = 0    j = i + 2    water\_acc = 0    acc = 0    water = 0    *while* j < len(columns):        col1 = columns\[i]        col2 = columns\[j]        print(col1, col2)        *if* col1 == 0:            i += 1            j = i + 2        *elif* col1 > col2:            water = min(col1,col2) \* (j-i-1) - sum(columns\[i+1:j])            *if* water > 0:                acc += water  *#### accumulative until col1 moves to a bigger column*            j += 1        *else*: *### col2 >= col1*            water = min(col1,col2) \* (j-i-1) - sum(columns\[i+1:j]) - acc            acc = 0            i = j            j = i + 2                *if* water > 0:            water\_acc += water                print('water', water)        print('water\_acc', water\_acc)        *return* water\_acc

Albert Johanson

student•

Solucion con C#public class Solution { public int Trap(int[] height) { int left = 0; int rigth = height.Length - 1; int maxLeft = height[left]; int maxRigth = height[rigth]; int maxWater = 0; while(left < rigth) { if(maxLeft > maxRigth) { rigth--; } else { left++; } if(maxLeft - height[left] > 0) { maxWater = maxWater + maxLeft - height[left]; } else if (maxRigth - height[rigth] > 0) { maxWater = maxWater + maxRigth - height[rigth]; } if(height[left] > maxLeft) { maxLeft = height[left]; } if(height[rigth] > maxRigth) { maxRigth = height[rigth]; } } return maxWater; }}```js public class Solution { public int Trap(int[] height) { int left = 0; int rigth = height.Length - 1; int maxLeft = height[left]; int maxRigth = height[rigth]; int maxWater = 0;

    while(left < rigth) {
        if(maxLeft > maxRigth) {
            rigth--;
        } else {
            left++;
        }

        if(maxLeft - height[left] > 0) {
            maxWater = maxWater + maxLeft - height[left];
        } else if (maxRigth - height[rigth] > 0) {
            maxWater = maxWater + maxRigth - height[rigth];
        }

        if(height[left] > maxLeft) {
            maxLeft = height[left];
        }

        if(height[rigth] > maxRigth) {
            maxRigth = height[rigth];
        }
    }

    return maxWater;
}

}

Javier Villegas

student•

Una solución en php

function calculate_rain($alturas): int{
    $p1 = count($alturas )-3;
    $p2 = count($alturas )-2;
    $p3 = count($alturas )-1;
    $water = 0;
    do{
        if($alturas[$p3]<=$alturas[$p2]){
            $p3--;
            $p2--;
            $p1--;
        }elseif( $alturas[$p3]>$alturas[$p2] && $alturas[$p1]<=$alturas[$p2]){
            $p1--;
        }
        if($alturas[$p3]>$alturas[$p2] && $alturas[$p1] > $alturas[$p2]){
            //Calculamos agua
            $min_altura = min($alturas[$p3],  $alturas[$p1]);
            for($i = ($p1+1); $i < $p3; $i++){
                $water = $water + ($min_altura - $alturas[$i]);
            }
            $p3 = $p1;
            $p2 = $p1 - 1;
            $p1 = $p1 - 2;
        }
    }while(isset($alturas[$p1]));
    return $water;
}

Miguel Angel Reyes Moreno

student•

Admito que hice un poco de trampa. Le pedí a chat gpt que me ayudar a entender el problema, pero le dije que no me diera la solución ni me arrojara el código.

Les comparto mi solución que probé en leetcode y pasó las pruebas:

const trap = (height: number\[]): number => {  if (height.length < 3) {    return 0;  }
&#x20; let leftPointer = 0  let rightPointer = height.length - 1
&#x20; const heightsLeft: number\[] = \[]  let maximumHeightLeft = 0
&#x20; const heightsRight: number\[] = \[]  let maximumHeightRight = 0
&#x20; let waterSquares = 0
&#x20; while (leftPointer < rightPointer) {    if (maximumHeightLeft < height\[leftPointer]) {      maximumHeightLeft = height\[leftPointer]    }    if (maximumHeightRight < height\[rightPointer]) {      maximumHeightRight = height\[rightPointer]    }
&#x20;   if (height\[leftPointer] < height\[rightPointer]) {      heightsLeft.push(height\[leftPointer])      waterSquares += maximumHeightLeft - height\[leftPointer]      leftPointer += 1    } else {      heightsRight.push(height\[rightPointer])      waterSquares += maximumHeightRight - height\[rightPointer]      rightPointer -= 1    }  }
&#x20; return waterSquares;}
console.log(trap(\[0,1,0,2,1,0,1,3,2,1,2,1])) //\* = 6console.log(trap(\[4,2,0,3,2,5])) //\* = 9

Marcos Mesias

student•

Ya solucione el problema, y lo hice en menos de 24 horas lo cual me sorprende a mi mismo, cada vez estoy mas cerca de resolver estos problemas tan complejos en una hora o menos que es lo ideal.

Para resolver el problema, lo primero como siempre, es hacer una observación profunda al problema y la salida del resultado, al principio uno piensa que es un problema de geometría y que toca calcular el área, pero no es así, no es un problema de geometría, mas bien es un problema de aritmética básica, de suma y resta. Claro toca tener dos punteros. Solo piensen que en cubo tiene que llenarse de agua.

Mi solución es O(n) Lineal.

Kengya Moncada

student•

const arr = [0,1,0,2,1,0,1,3,2,1,2,1];

function maxWater(){
let n = rr.length;
let maxL = 0;
let maxR = 0;
let p1 = 0;
let p2 = n - 1;
let water = 0;

if(n <= 2) return 0;

    while(p1 < p2){
      if(arr[p1] < arr[p2]){
        if(arr[p1] > maxL){
          maxL = arr[p1]
        }else{
          water += maxL - arr[p1]
        }
        p1++
      }else{
        if(arr[p2] > maxR){
          maxR = arr[p2]
        }else{
          water += maxR - arr[p2]
        }
        p2--
      }
    }
     return water
}

maxWater();
```Tomé varios dias intentando, no me resultaba asi que vi un recurso y tome la idea...

Arley Santiago

student•

Hello there this one is my solution:

https://drive.google.com/file/d/18UgBcwzbklbSFZjMDy35SmZfAstfl4NC/view?usp=sharing

Arley Santiago

student•

Santiago Amaya

student•

def rain_water(a):
    p = 0
    p1 = p + 1
    areas = []
    while p < len(a)-1 and p1 < len(a) - 1 :
        print(f'p = {p} a[p] => {a[p]}, p1 = {p1} a[p1] => {a[p1]}')
        if  a[p] > a[p1]:
            p += 1 
            height = max(a[p], a[p1]) 
            lenght = 1
            print(f'height = {height}, lenght = {lenght}')
            area = height * lenght
            areas.append(area)
            print(f'area = {area}')
        else: 
              
            p += 1 
            lenght = 1 
            height = a[p] - a[p1]
            print(f'height = {height}, lenght = {lenght}')
            area = height * lenght
            areas.append(area)
            print(f'area = {area}')

            if p == len(a)-2:
                break

    water = sum(areas)        
    return water

a = [0,1,0,2,1,0,1,3,2,1,2,1]
print(rain_water(a))

Juan Esteban

student•

mi solución en go:

func trap(height []int) int {
	if len(height) == 0 {
		return 0
	}

	l, r := 0, len(height)-1
	maxL, maxR := height[l], height[r]
	res := 0
    sum := 0
	for l < r {
    fmt.Println(height[l], sum, height[r])
		if maxL < maxR {
			l++
			maxL = max(height[l], maxL)
			sum = min(maxR, maxL) - height[l]
		} else {
			r--
			maxR = max(height[r], maxR)
			sum = min(maxR, maxL) - height[r]
		}
    if sum <= 0 {
      sum = 0
    }
    res += sum
	}
	return res
}

Andrés Ariza

student•

const trappingRainWater = (arrayHeights) => {

  let i = 0;
  let j = arrayHeights.length - 1;

  let leftMax = arrayHeights[i]
  let rightMax = arrayHeights[j]

  let acummulator = 0;

  while (i < j) {

    if (leftMax <= rightMax) {
      let difference = leftMax - arrayHeights[i + 1]
      if (difference > 0) {
        acummulator += difference
      }
      if (difference < 0) {
        leftMax = arrayHeights[i + 1]
      }
      i += 1

    }
    else {
      let difference = rightMax - arrayHeights[j - 1]
      if (difference > 0) {
        acummulator += difference
      }
      if (difference < 0) {
        rightMax = arrayHeights[j - 1]
      }
      j -= 1
    }
  }

  return { acummulator }
}

const array = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

console.log(trappingRainWater(array))


const array2 = [0, 1, 0, 0, 0, 0, 0, 0, 0, 1]

console.log(trappingRainWater(array2))

Victor Hugo Vázquez Gómez

student•

Me costo muchas horas llegar a esta solucion, lo podia hacer en papel pero no podia llegar a la solucion en codigo asi que me di por vencido y busque la solucion en google T-T

Puse dos apuntadores a extremos del arreglo que se van a estar moviendo durante todo el bucle while.

Otras dos variables que van a tomar el valor maximo de la izquierda y derecha. Solo van a cambiar cuando vean un valor mas grande.

Ahora dentro del bucle while hago una comparacion de que valor Maximo es el menor. El que sea el menor es el que voy a escoger, muevo mi apuntador a la direccion que se requiera para apuntar al siguiente valor y poder medir el agua.

Despues, para medir el agua tengo que determinar si el valor minimo de los Maximos que tome es mayor que el valor del apuntador actual, tomo ese maximo, si no, ese apuntador actual se convierte en mi nuevo maximo izq/derecho.

Para finalizar, resto ese nuevo valor maximo con el valor del apuntador actual.

Codigo en Typescript:

export const trappingRainWater = (height: number[]): number => {
  let water = 0;

  let ml = height[0];
  let mr = height[height.length - 1];

  let pl = 0;
  let pr = height.length - 1;

  while (pr > pl) {
    if (ml < mr) {
      pl++;
      ml = Math.max(ml, height[pl]);
      water += ml - height[pl];
    } else {
      pr--;
      mr = Math.max(mr, height[pr]);
      water += mr - height[pr];
    }
  }

  return water;
};

Alberto Perdomo

student•

Esta es mi solucion en python:

def trapping_rain_water(list=[0, 1, 0, 2, 1, 0, 3, 2, 1, 2, 1]):
  total_area = 0
  p1=0
  p2=1
  while p2 < len(list)+1:
    total_area += min(list[p1], list[p2]) * (p2-p1)
    if list[p1] < list[p2]:
      p1 += 1
    else:
      p2 += 1
    p1 = p2
    p2 += 1
  return total_area + 1

José Juan García Mendoza

student•

Asi queda mi implementación en Java

public static int trappedWater(int [] heightList){
    int p1=0;
    int p2=1;
    int p3=0;
    int temp = 0;
    while(p2<heightList.length-1){

        if(heightList[p1]>heightList[p2]){
            temp += heightList[p1] - heightList[p2];

        }else{
            p1=p2;
            temp=0;
        }

        if(p3<temp){
            p3=temp;
        }
        p2++;
    }
    return p3;
}