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

Solución de Container With Most Water

13/35
Recursos

Aportes 14

Preguntas 1

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

o inicia sesión.

Se me hacía raro porque la profe había puesto P2 + P1 +1 si la posición por donde la miro me daba 4, posición 7 - posición 3 = 4, no tenia que sumar nada, o si fuera desde el cero seria posición 6 - 2 = 4, en la siguiente clase me dare cuenta que paso con ese +1

Esta es mi solución en Java:

public class ContainerWithMostWaterOptimizado {

    public static int containerWithMostWater(int[] alturas) {
        int mejorArea = 0;
        int p1 = 0;
        int p2 = alturas.length - 1;

        while (p1 != p2) {
            int altura = Math.min(alturas[p1], alturas[p2]);
            int ancho = p2 - p1;
            int area = altura * ancho;

            if (area > mejorArea) {
                mejorArea = area;
            }

            if (alturas[p1] < alturas[p2]) {
                p1++;
            } else {
                p2--;
            }
        }

        return mejorArea;
    }

    public static void main(String[] args) {
        int[] alturas = {1, 8, 6, 2, 5, 4, 8, 3, 7};

        int areaMax = containerWithMostWater(alturas);
        System.out.println(areaMax);
    }
}

La verdad hubiera tardado eones en llegar a una solución O(n) como la profe, esto fue lo que entendi:

Ir calculando el area mas grande posible para el apuntador de menor valor.

Guarda un area global que cambia solo si el area calculada en el paso anterior es mayor, tomando este valor.

El apuntador que tenga menor valor se va a mover hacia el centro ya que no hay posibilidad de conseguir un area mayor, porque la distancia hacia el otro apuntador solo va a disminuir (por ejemplo cuando tenemos el valor 1, si descartaramos el valor 7, la distancia entre apuntadores seria n-2 por tanto el area para ese elemento seria menor que la que ya conseguimos 1(n-1) > 1(n-2)).

Cuando los dos apuntadores estan en la misma posicion se termina el algoritmo.

```js # Time Complexity: O(n) # Space Complexity: O(1) def water_area_faster(heights) max_area = -Float::INFINITY left = 0 right = heights.length - 1 while left <= right width = right - left left_height = heights[left] right_height = heights[right] height = [left_height, right_height].min area = width * height max_area = [max_area, area].max if left_height < right_height left += 1 next end if left_height > right_height right -= 1 next end if left + 1 == right || right - 1 == left break end if left_height == right_height if heights[left + 1] >= heights[right - 1] left += 1 next else right -= 1 next end end end max_area end ```# Time Complexity: O(n)# Space Complexity: O(1) def water\_area\_faster(heights) max\_area = -Float::INFINITY left = 0 right = heights.length - 1 while left <= right width = right - left left\_height = heights\[left] right\_height = heights\[right] height = \[left\_height, right\_height].min area = width \* height max\_area = \[max\_area, area].max if left\_height < right\_height left += 1 next end if left\_height > right\_height right -= 1 next end if left + 1 == right || right - 1 == left break end if left\_height == right\_height if heights\[left + 1] >= heights\[right - 1] left += 1 next else right -= 1 next end end end max\_areaend ![](https://static.platzi.com/media/user_upload/image-ce44c64a-ba52-4552-bfec-818ec4cd3d2e.jpg)

Mi solucion en typescript:

export const containerWithMostWater = (heights: number[]): number => {
  let water: number = 0;

  let p1: number = 0;
  let p2: number = heights.length - 1;

  while (p2 > p1) {
    let currentWater: number = (p2 - p1) * (heights[p1] < heights[p2] ? heights[p1] : heights[p2]);

    if (currentWater > water) water = currentWater;

    // If values are the same, move the two pointer
    if (heights[p1] === heights[p2]) {
      p1 = p1 + 1; // move pointer #1 to the right
      p2 = p2 - 1; // move pointer #2 to the left;
    } else if (heights[p1] > heights[p2]) {
      p2 = p2 - 1; // move pointer #2 because is the least tall
    } else if (heights[p1] < heights[p2]) {
      p1 = p1 + 1; // move pointer #1 because is the least tall
    }
  }

  return water;
};

Mi implementación en Java

public static int calculateWater(int[] pileNumbers){
    int p1=0;
    int p2=pileNumbers.length-1;
    int p3=0;
    int temp = 0;
    while(p1<p2){
        temp = Math.min(pileNumbers[p1], pileNumbers[p2])*(p2-p1);
        if(p3<temp)
            p3 = temp;
        if(p1<p2){
            p1++;
        }else{
            p2--;
        }
    }
    return p3;
}

comparto mi solucion

function ContainerWithMostWater(list) {
    let result = 0
    let counter1 = 0
    let counter2 = list.length - 1

    const calculateWater = (height1, height2, distance) => {
        if (height1 < height2) return height1 * distance
        return height2 * distance
    }

    for (let index = 0; index < list.length; index++) {
        if (result < calculateWater(list[counter1], list[counter2], counter2 - counter1)) result = calculateWater(list[counter1], list[counter2], counter2 - counter1)
        if (list[counter1] < list[counter2]) counter1++
        else counter2++
    }

    return result
}

La verdad no sé si hay algo que se me está pasando por alto, pero si los dos apuntadores se encuentran en el centro y ahi termina la ejecución, no voy a estar considerando todas las posibilidades: por ejemplo, si el input es [1, 1, 1, 1, 1, 100, 100], nunca voy a calcular el area entre 100 y 100, o sí? expliquenme porfas jajaj. Lo que yo hice es mover un solo apuntador y cuando llegue al otro extremo donde esta el segundo apuntador, volver el primero a 0 y disminuir el segundo y terminar cuando el segundo apuntadort deje de ser mayor a 0. Mi solución en js:

function containerWithMostWater(nums){
let p1 = 0,
p2 = nums.length - 1
resultado = 0

while(0 < p2) {
    if(p1 < p2){
        let altura = Math.min(nums[p2], nums[p1]),
        ancho = nums.slice(p1, p2).length
        area = ancho * altura
        console.log("p2", nums[p2], "p1", nums[p1]);
        console.log("altura", altura, "ancho", ancho, area)
        if(area > resultado){
            resultado = area
        }
        p1++
    } else {
        p1 = 0
        p2--
    }
}

return resultado

}

Mi solución en C++ 😄

#include <bits/stdc++.h>
using namespace std;

int containerWithMostWater(int input[],int arraySize);
int calculateArea(int lengt, int width);
int updateVariable(int maxArea, int currentArea);

int main(){
    //Change the values of the array.
    int array1[]= {1, 8, 6, 2, 5, 4, 8, 3, 7};
    //Variable to storage the number of elements inside the array.
    int arraySize= sizeof(array1)/sizeof(array1[0]);
                                                //Calling the Function
    cout << "The Maximum possible area is: " << containerWithMostWater(array1, arraySize) << endl;
    return 0;
}

int containerWithMostWater(int input[], int arraySize){
    //Pointer 1
    int p1= 0;
    //Pointer 2
    int p2= arraySize-1;
    //MaxArea is a variable to save the maximum possible area
    //that a container can storage.
    int maxArea= 0;

    for (int i = 0; i < arraySize; i++)
    {
        //Comparisons to check which pointer has to be updated.
        if(input[p1]<input[p2]){
            maxArea = updateVariable(maxArea, calculateArea(input[p1], p2-p1));
            p1+=1;
        }else if(input[p1]>input[p2]){
            maxArea= updateVariable(maxArea, calculateArea(input[p2], (p2-p1)));
            p2-=1;
        }else{
            //This option is made for the case input[p1]==input[p2].
            maxArea= updateVariable(maxArea, calculateArea(input[p2], (p2-p1)));
            p1+=1;
            p2-=1;
        }
    }
    //Returns the maximum Area.
    return maxArea;
}

int calculateArea(int lengt, int width){
    //Returns the area of a rectangle, which the shape that the container has.
    return lengt*width;
}

int updateVariable(int maxArea, int currentArea){
    //Returns the maximum value between the current calculated area and the maxArea
    //from the previous iteration.
    if(maxArea<currentArea){
        maxArea= currentArea;
    }
    return maxArea;
}

No había entendido este tema, asta este ejercicio, la verdad estas explicaciones visuales de como funcionan las variables y los cálculos que se hacen ayudan demasiado.

Adjunto mi posible solucion

    public static int WithMostWater(int[] hights)
    {

        int left = 0;
        int right = hights.Length - 1;

        int maxAreaFound = 0;

        while (left != right)
        {
            int distance = right - left;
            int min = Math.Min(hights[left], hights[right]);
            int area = distance * min;
            if (area > maxAreaFound) maxAreaFound = area;
            left++;
        }

        return maxAreaFound;
    }

este problema yo lo había echo con python así:

def maxArea(self, height: List[int]) -> int:
        n = len(height)
        left = 0
        right = n-1
        base = n-1
        max_value = 0

        while base > 0:
            if height[left] <= height[right]:
               max_v = base*height[left]
               if max_value < max_v:
                   max_value = max_v
               left += 1
                

            elif height[left] > height[right]:
                max_v = base*height[right]
                if max_value < max_v:
                    max_value = max_v
                right -= 1

            base -= 1

        return max_value

Solución en python (al menos como lo entendí yo)

def biggestCont(arr):
    bi = 0 # index of biggest num. before given position
    maxArea = -1
    for i in range(len(arr)):
        area = min(arr[i],arr[bi])*(i-bi)
        if area > maxArea:
            maxArea = area
        if arr[i] > arr[bi]:
            bi = i
    return maxArea

# T = O(n)
# S = O(1)    

arr = [1,8,6,2,5,4,8,3,7]
print(biggestCont(arr))

Ruby:

def most_water_resolver(hs)
  final_area = 0
  hs.each_with_index do |h, index|
    (index+1...hs.length).each do |j|
      hight = [hs[index], hs[j]].min
      base = j - index
      area = hight*base
      final_area = [final_area, area].max
    end
  end
  final_area
end

p most_water_resolver([1, 8, 6, 2, 5, 4, 8, 3, 7])