Introducci贸n

1

Arrays y Strings para resolver algoritmos avanzados

2

Arrays y Strings en detalle

Dos Apuntadores

3

Patr贸n de Dos Apuntadores

4

Verifying Alien Dictionary: an谩lisis del problema

5

Soluci贸n de Verifying Alien Dictionary

6

Playground: Verifying Alien Dictionary

7

Programando Verifying Alien Dictionary con JavaScript

8

Merge Two Sorted Lists: an谩lisis del problema

9

Soluci贸n de Merge Two Sorted Lists

10

Playground: Merge Two Sorted Lists

11

Programando Merge Two Sorted Lists con Python

12

Container With Most Water: an谩lisis del problema

13

Soluci贸n de Container With Most Water

14

Playground: Container with Most Water

15

Programando Container With Most Water con Java

16

Reto: Trapping Rain Water

17

Ejercicios recomendados de Dos Apuntadores

18

Ejercicios resueltos de Dos Apuntadores

Ventana Deslizante

19

Patr贸n de Ventana Deslizante

20

Longest Substring Without Repeating Characters: an谩lisis del problema

21

Soluci贸n de Longest Substring Without Repeating Characters

22

Playground: Longest Substring Without Repeating Characters

23

Programando Longest Substring Without Repeating Characters con Python

24

Ejercicios recomendados de Ventana Deslizante

25

Ejercicios resueltos de Ventana Deslizante

B煤squeda Binaria

26

Algoritmo de B煤squeda Binaria

27

Search in Rotated Arrays: an谩lisis del problema

28

Soluci贸n de Search in Rotated Arrays

29

Playground: Search in Rotated Arrays

30

Programando Search in Rotated Arrays

31

Search 2D Array Matrix: an谩lisis del problema

32

Soluci贸n de Search 2D Array Matrix

33

Playground: Search 2D Array Matrix

34

Programando Search 2D Array Matrix

Pr贸ximos pasos

35

Toma el Curso Avanzado de Algoritmos: Estructuras de Datos Lineales

No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Reto: Trapping Rain Water

16/35
Recursos

Aportes 19

Preguntas 0

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

Una soluci贸n con complejidad espacial O(n), es menos eficiente que la de dos punteros pero me ayud贸 a entender la l贸gica de la soluci贸n. Les recomiendo este video para entender m谩s si saben ingl茅s: https://www.youtube.com/watch?v=ZI2z5pq0TqA

def rainWaterV1(arr):
    maxLeft = [0]*len(arr)
    maxRight = [0]*len(arr)
    total = 0
    # get max value at left of i
    maxVal = -1
    for i in range(1, len(arr)):
        maxVal = max(arr[i-1], maxVal)
        maxLeft[i] = maxVal
    maxVal = -1
    # get max value at right of i
    for i in range(len(arr)-2, -1, -1):
        maxVal = max(arr[i+1], maxVal)
        maxRight[i] = maxVal
    # get sum of areas
    for i in range(len(arr)):
        area = min(maxLeft[i], maxRight[i])-arr[i]
        if area > -1:
            total += area
    return total

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
}
```python 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)) ```
mi soluci贸n en go: ```js 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 } ```
```js 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)) ```

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 soluci贸n en javascript, creo que puede optimizarse m谩s, pero fue la primera que logr茅:

<class Main {
    aguaAtrapada(alturas){
        let area = 0; // 6
        let izquierda = 0; // 4(1)
        let derecha = alturas.length - 1; //11(2)
        let maxIzquierda = 0; //2
        let maxDerecha = 0; //1


        while(izquierda < derecha){
            if(alturas[izquierda] <= alturas[derecha]){
                if(alturas[izquierda] > maxIzquierda){
                    maxIzquierda = alturas[izquierda];
                }else{
                    area += maxIzquierda - alturas[izquierda];
                }
                izquierda++;
            }else{
                if(alturas[derecha] > maxDerecha){
                    maxDerecha = alturas[derecha];
                }else{
                    area += maxDerecha - alturas[derecha];
                }
                derecha--;
            }
        }

        return area;
};
}
const instancia = new Main();
const ListaAlturas = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
const cantidadAgua = instancia.aguaAtrapada(ListaAlturas);
console.log(cantidadAgua);> 

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))