Algoritmo para Trapping Rainwater en Python

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;
} 

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

👨‍💻 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
}

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;
};

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

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;
}

Les dejo mi solución en PHP, lo único que me dí cuenta después es que nos podemos ahorrar los cálculos en los extremos, porque fuera de los extremos nunca hay pared que retenga el agua, entonces no es necesario calcular ahí. Ya no lo corregí, la complejidad T no cambia con ese detalle. Yo digo que T = O(n), S=O(1), aunque no estoy al 100% seguro. Lo que sí hice fué probar con varios casos y todos funcionaron. En el código están esos casos de prueba.

<
    <h1>Trapping Rain Water..</h1>
    <?php
    $heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
    // $heights = [2,0,2];
    // $heights = [3, 0, 2, 0, 4];

    function water($heights)
    {
        $p1 = 0;
        $p2 = count($heights) - 1;
        $water = 0;
        $maxLeft = 0;
        $maxRight = 0;
        while ($p1 < $p2) {
            echo "BEFORE: ". " p1:".$p1.", p2:".$p2.", maxLeft:" . $maxLeft .", maxRight:" . $maxRight . ", actualLeft:" . $heights[$p1] .", actualRight:" . $heights[$p2] . ", water:" . $water. "\n";
            if ($heights[$p1] <= $heights[$p2]) {
                $maxLeft = ($heights[$p1] > $maxLeft) ? $heights[$p1] : $maxLeft;
                $water += $maxLeft - $heights[$p1];
                $p1++;
            } else {
                $maxRight = ($heights[$p2] > $maxRight) ? $heights[$p2] : $maxRight;
                $water += $maxRight - $heights[$p2];
                $p2--;
            }
            // echo "AFTER: ". " p1:".$p1.", p2:".$p2.", maxLeft:" . $maxLeft .", maxRight:" . $maxRight . ", actualLeft:" . $heights[$p1] .", actualRight:" . $heights[$p2] . ", water:" . $water . "\n";
        }
        return $water;
    }
    echo water($heights);
    ?>
>

Siguiendo el ejemplo de la profe, parece demorase más, pero se queda mejor.

c#

int p1 = 0;
int p2 = alturas.Count() - 1;

int maxL = alturas[0];
int maxR = alturas[alturas.Count() - 1];
int areaMaxima = 0;

while (p1 != p2)
{
    if (alturas[maxL] <= alturas[maxR])
    {
        int area = maxL - alturas[p1];

        if (area > 0) areaMaxima += area;

        p1 += 1;
        // calculamos la maxima altura de left
        maxL = Math.Max(maxL, alturas[p1]);

    }
    else
    {
        int area = maxR - alturas[p2];

        if (area > 0) areaMaxima += area;

        p2 -= 1;

        // calculamos la maxima altura de rigth
        maxR = Math.Max(maxR, alturas[p2]);

    }
}

Console.WriteLine(areaMaxima);

Mi propuesta utilizandon c#

static int getTrappedWater(int[] list_of_heights)
{
    int left = 0;
    int right = list_of_heights.Length - 1;
    int leftMaxHeight = list_of_heights[left];
    int rightMaxHeight = list_of_heights[right];
    int trappedWater = 0;

    while(left <= right)
    {
        if(list_of_heights[left] < list_of_heights[right])
        {
            if (list_of_heights[left] >= leftMaxHeight) 
            {
                leftMaxHeight = list_of_heights[left];
            }
            else
            {
                trappedWater += leftMaxHeight - list_of_heights[left];
            }
            left++;
        }
        else
        {
            if (list_of_heights[right] >= rightMaxHeight)
            {
                rightMaxHeight = list_of_heights[right];
            }
            else
            {
                trappedWater += rightMaxHeight - list_of_heights[right];
            }
            right--;
        }
    }
    return trappedWater;
}

Mi solución en Java haciendo uso de dos punteros. Tiene complejidad temporal O(n) y complejidad espacial O(1).

public class Main {
    public static void main(String[] args) {
        int[] inputArray= {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println("The maximum value of trapped rain water is: " + trappedRainWaterCalculator(inputArray));
    }
    public static int trappedRainWaterCalculator(int[] array){
        
        int trappedWater=0;
        int l= 0,  r= array.length-1;
        int leftMax= array[l];
        int rightMax= array[r];

        while(l < r){
            if (leftMax < rightMax){
                l += 1;
                leftMax= Math.max(leftMax, array[l]);
                trappedWater+= leftMax - array[l];
            }else{
                r -= 1;
                rightMax= Math.max(rightMax, array[r]);
                trappedWater+= rightMax - array[r];
            }
        }
        return trappedWater;
    }
}

comparto mi solución en js, la verdad que la parí masomenos. Alguien me confirma si está bien lo de la complejidad? yo creo que sí pero no estoy seguro. Gracias gente a seguir estudiando!!!

function trappingRainWater(nums){
let p1 = 0,
p2 = p1 + 1
resultado = 0
area = 0
areaNeg = 0

while(p1 < nums.length - 1){
    if (nums[nums.length - 1] <= nums[nums.length - 2]) {
        nums.pop()
    } else if(nums[0] <= nums[1]){
        nums.shift()
    } else {
        if (nums[p1] > nums[p2]) {
            if (p2 === nums.length - 1 && nums[p1] > nums[p2]) {
                area = nums[p2] * nums.slice(p1 + 1, p2).length
                resultado = resultado + area - areaNeg
                break
            } else {
                areaNeg = areaNeg + nums[p2]
                p2++
            }
        } else if (nums[p1] <= nums[p2]) {
            if(nums.slice(p1 + 1, p2).length > 0) {
                area = nums[p1] * nums.slice(p1 + 1, p2).length
                resultado = resultado + area - areaNeg
            }

            p1++
            p2 = p1 + 1
            areaNeg = 0
        }
    }
}

return resultado

}

Mi solución en JS

function trappingRainWater (numbers) {
    /* 
        T = O(n)
        S = O(1)
    */
    let totalTrappedWater = 0;
    let pivot = 0;
    let temporalTrappedWater = 0
    for(let i = 0; i < numbers.length; i++){
        //Encontrar el pivot
        if(numbers[i] > numbers[i + 1] && numbers[i] > pivot){
            pivot = numbers[i];
        }
        //Si el número actual es menor al pivot, almaceno la cantidad temporal de agua acumulada
        if(numbers[i] < pivot){
            temporalTrappedWater += (pivot - numbers[i]);
        //Si el número actual es mayor o igual al pivot, sumo la cantidad temporal de agua acumulada
        //al total, en caso de que haya.
        } else {
            totalTrappedWater += temporalTrappedWater;
            //Una vez sumada la cantidad temporal al total, la restablezco en 0 para volver a acumular
            temporalTrappedWater = 0;
            //Como el numero actual es mayor al pivot, se reemplaza.
            pivot = numbers[i];
        }
    }
    return totalTrappedWater;
 }

//  console.log(trappingRainWater([0,1,0,2,3,1,1,0,4,8,6,3,2,1,0,8])) Output = 36
//  console.log(trappingRainWater([9,7,5,3,1,0,1,3,5,7,9])) Output= 49

Code en Javascript

let contenedor = [0,1,0, 2,1,0, 1,3,2, 1,2,1]

function funTotalSinAgua(contenedor){
    let totalSinAgua = 0;
    let i
    for(i = 0; i < contenedor.length; i++) {
        totalSinAgua = totalSinAgua + contenedor[i];
    }
    return totalSinAgua
}

function funRetoTrappingRainWater(contenedor){

    const valorMasAlto= Math.max(...contenedor)
    const indexMxValor = contenedor.indexOf(valorMasAlto);

    let totalConAgua_derecha = 0
    let totalConAgua_izquerda = 0

    let max_derecha = 0
    let max_izquerda = 0

    let i
    for (i = 0; i <= indexMxValor; i++) {
        if(max_izquerda < contenedor[i]){
            max_izquerda = contenedor[i]
        }
        totalConAgua_izquerda = totalConAgua_izquerda + max_izquerda
    }
    
    let j
    for (j = contenedor.length - 1; indexMxValor < j; j--) {
        if(max_derecha < contenedor[j]){
            max_derecha = contenedor[j]
        }
        totalConAgua_derecha = totalConAgua_derecha + max_derecha
    }
    
    return (totalConAgua_izquerda + totalConAgua_derecha - funTotalSinAgua(contenedor))
}

console.log(funRetoTrappingRainWater(contenedor))