Resolver el problema "Container with Most Water" en Python

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

Resumen

¿Cómo encontrar el contenedor con más agua?

Encontrar el contenedor con más agua es un desafío común en problemas de programación competitiva y entrevistas técnicas. Este problema se centra en identificar las dos líneas, con diferentes alturas, que forman un contenedor capaz de almacenar la máxima cantidad de agua posible. A continuación, descubrirás cómo abordar este problema paso a paso.

¿Qué representa el problema?

Imagina que tienes una lista de números que simbolizan las alturas de un conjunto de líneas verticales. Tu tarea es seleccionar dos de estas líneas para formar un contenedor que almacene la máxima cantidad de agua. Este contenedor se representará como un rectángulo entre las dos líneas seleccionadas, con la altura del rectángulo determinada por la menor de las dos líneas. Vamos a explicar esto con un ejemplo:

Lista de alturas: [1, 8, 6, 2, 5, 4, 8, 3, 7]
La mayor cantidad de agua que se puede almacenar es 49.

¿Por qué es importante este problema?

Resolver el problema "Container with Most Water" no solo te ayuda a mejorar tus habilidades en algoritmos y estructuras de datos, sino que también te prepara para afrontar problemas similares en entrevistas técnicas y hackatones. Además, fomenta el pensamiento analítico y la capacidad para optimizar soluciones.

¿Cómo puedes resolverlo?

Para abordar este problema, puedes utilizar un enfoque bidireccional conocido como el método de dos punteros. Aquí hay una guía paso a paso para implementar esta estrategia:

Inicializar dos punteros: Coloca un puntero al inicio de la lista y otro al final.
Calcular el área: Calcula el área del contenedor formada por las líneas en las posiciones de estos punteros. El área se calcula utilizando la fórmula: (posición_derecha - posición_izquierda) * min(altura_izquierda, altura_derecha).
Actualizar la máxima cantidad de agua: Compara el área calculada con la máxima cantidad almacenada hasta ese momento y actualiza este valor si el área actual es mayor.
Mover punteros: Para maximizar el área, mueve el puntero que apunta a la línea más baja hacia el otro puntero con la esperanza de encontrar una línea más alta que potencialmente cree un área mayor.
Repetir el proceso: Continúa este proceso hasta que los dos punteros se encuentren.

Implementación en código

Aquí tienes un esbozo de cómo podría verse este algoritmo en Python:

def max_area(height):
    left = 0
    right = len(height) - 1
    max_water = 0

    while left < right:
        # Calculamos el área actual
        width = right - left
        current_height = min(height[left], height[right])
        current_area = width * current_height
        
        # Actualizamos el máximo de agua almacenada
        max_water = max(max_water, current_area)
        
        # Mover punteros
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

Sugerencias y consejos

Optimización: Aunque podrías intentar un enfoque de fuerza bruta, el método de dos punteros es más eficiente, con complejidad de tiempo lineal (O(n)).
Pruebas exhaustivas: Implementa casos de prueba para asegurarte de que tu solución maneje distintas variaciones, como listas con alturas similares o cuando solo hay dos líneas.

Este problema es una excelente oportunidad para poner a prueba tus habilidades de resolución de problemas. Estudia su lógica, implementa el algoritmo, y verás cómo mejorarás no solo tu comprensión de este problema, sino también tus capacidades para enfrentar desafíos algorítmicos en general. ¡Sigue adelante y mantiene siempre la curiosidad viva!

Juan Esteban

student•

Esta imagen puede servir para entender el problema

El sombreado azul representa la cantidad de agua, y esta es el área que hay que hallar. Se multiplica el área del mas bajo (7) por la distancia entre los dos (7): 7 * 7 = 49

Gabriel Revelo

student•

muy util

Juan Pablo Reina Gutierrez

student•

Excelente, gracias, muy útil.

Alberto Perdomo

student•

Cuando yo era estudiante de ingeniería mecánica, este problema se solucionaba con integrales. La matemática booleana y la programación lo hacen ver tan fácil que es impresionante.

De verdad los computadores, son un invento de la humanidad al mismo nivel de la rueda, diría yo que incluso más.

Neider Lopez

student•

Holaa Esta es mi solución en java

package public com.lpzneider.algoritmos; class ContainerWithMostWater { public static int operationContainerWithMostWater(Integer[] list){ int multiplicando = 0; int multiplicador = 0; int producto = 0; int p2 = list.length - 1; int result = 0; for(int i = 0; i <= p2; i++){ for(int j = i + 1; j <= p2; j++){ multiplicando = Math.``min``(list[i], list[j]); multiplicador = j - i; producto = multiplicando * multiplicador; result = Math.``max``(result, producto); } } return result; } public static void main(String[] args) { Integer[] lineas = {9,8,6,2,5,4,8,3,7}; System.``out``.println(``operationContainerWithMostWater``(lineas)); } }

Marcos Mesias

student•

Lo logre solucionar, creo mi solución tiene una dificulta de O(n*2), no la pude hacer lineal, de un solo ciclo, pero la clave esta en entender que el problema es rectangulo, y toca calcular base x altura y sacar el area. Las alturas son los valores de la lista y la base son los indices de la lista. Lo importante es la altura y encontrar una altura igual o superior y sacar el area del rectangulao. Ejmplo si la altura es 1 y la siguiente altura es 8. entonces altura = 1 y base = 1 y el area seria = 1. En forma decendente seria asi. Altura 7 y la siguiente altura mas alta seria 8 y el 8 esta en el indice 2, seri altura = 7 base = 2, area = 14. El siguiente 8 esta en el 7 y seria altura 7 base 7, area igual a 49.

Samuel José Moreno

student•

#include <iostream>

using namespace std;

int main() {
    int array[] = {1,8,6,2,5,4,8,3,7};
    int longitud = sizeof(array)/sizeof(array[0]);
    int maximo = 0;
    for (int i = 0; i < longitud; i++) {
        int elemento1 = array[i];
        for (int j = i + 1; j <= longitud; j++) {
            int elemento2 = array[j];
            int base = j - i;
            int area;
            if (elemento2 < elemento1) { 
                area = base * elemento2;
            } else {
                area = base * elemento1;
            }#include <iostream>


using namespace std;


int main() {

    int array[] = {1,8,6,2,5,4,8,3,7};

    int longitud = sizeof(array)/sizeof(array[0]);

    int maximo = 0;

    for (int i = 0; i < longitud; i++) {

        int elemento1 = array[i];

        for (int j = i + 1; j <= longitud; j++) {

            int elemento2 = array[j];

            int base = j - i;

            int area;

            if (elemento2 < elemento1) { 

                area = base * elemento2;

            } else {

                area = base * elemento1;

            }

            //cout << i << " " << j << ": " << area << endl;

            if (area > maximo) {

                maximo = area;

    

            }

        }

    }  

    cout << maximo << endl;

    

    

    

    

    return 0;

}
            //cout << i << " " << j << ": " << area << endl;
            if (area > maximo) {
                maximo = area;
    
            }
        }
    }  
    cout << maximo << endl;
    
    
    
    
    return 0;
}

Frandel Corporan Rodríguez

student•

no entendi este problema

Usuario anónimo

user•

Pues me costo más de 15 minutos para poder plantear una solución. Al final la solución que implementé fue hacer una comparación del primer elemento con sus siguientes elementos e ir registrando el área. A pesar de que solo utilizo un ciclo creo que en cuanto a tiempo sería de n^2, esto por la cantidad de iteraciones que hago sobre la lista.

Aquí dejo mi solución en JSconst getBiggestLines = (lines) => {

let firstPointer = 0;

let lastPointer = lines.length - 1;

let biggestArea = 0;

while (firstPointer < lines.length - 1) {

if (lastPointer - firstPointer === 1) {

lastPointer = lines.length - 1;

firstPointer += 1;

} else {

const firstLine = lines[firstPointer];

const lastLine = lines[lastPointer];

const area = Math.min(firstLine, lastLine) * (lastPointer - firstPointer);

if(area > biggestArea) {

biggestArea = area;

}

lastPointer -= 1;

}

return biggestArea;

};:

const getBiggestLines = (lines) => {
  let firstPointer = 0;
  let lastPointer = lines.length - 1;
  let biggestArea = 0;

  while (firstPointer < lines.length - 1) {

    if (lastPointer - firstPointer === 1) {
      lastPointer = lines.length - 1;
      firstPointer += 1;
    } else {
      const firstLine = lines[firstPointer];
      const lastLine = lines[lastPointer];
      const area = Math.min(firstLine, lastLine) * (lastPointer - firstPointer);
      
      if(area > biggestArea) {
        biggestArea = area;
      }
      
      lastPointer -= 1;
    }
  }
  return biggestArea;
};

Victor Hugo Vázquez Gómez

student•

Mi solucion despues de muchas horas de estar intentando resolver otro algoritmo que de plano no iba a funcionar :(

/**

Two pointers (p1, p2), one at the start, one at the end.
- Calculate the water with distance (p2-p1) minus minum height. Save result in water
- if the two values are the same, move pointers (p1++) (p2--)
- if not, move the pointer of the minimum height
- if two pointers are the same value (points to the same value), finish the execution. */

Victor Alfredo Matzar Say

student•

En mi caso no entendí a la primera, decidí analizarlo un poco 😃 En otras palabras cada línea representa una pared del contenedor, y el área formada por el contenedor se puede calcular como el producto de distancia entre las líneas y la altura de la línea más baja. En el ejemplo [1,8,6,2,5,4,8,3,7], comparan 8 y 7, su distancia la vemos de índice 1 al índice 8, por lo cual su distancia es 7, mientras que altura sería la más baja que es 7. Multiplicando 7 * 7 = 49.

El área formada por el contenedor depende tanto de la altura de las líneas como de la distancia entre ellas. En el caso de las líneas de altura 8 y 7, aunque su altura no es la máxima posible, la distancia entre ellas es la mayor de todas las combinaciones posibles, lo que resulta en un área mayor.

harol chumbe

student•

el problema esta mal planteado la cantidad de agua maxima es el volumen no el area . el area de la base la profeso la autodefine como 1 de ancho y de largo toma la distancia entre los puntos ... ¿No que se tenia que tener en claro todo antes de programar? ....
deberia corregir el enunciado.!

Nicolas Alpargatero

student•

Porque dices que está mal planteado si en ningún momento dijo area o volumen, dijo el rectángulo de la diferencia entre dos números, en un espacio 2D, si hablas de volumen estarías hablando de 3D, me imagino que será este mismo, pero agregándole un nivel de complejidad.

Juan Pablo Reina Gutierrez

student•

Mi primera solución en Java:

public class ContainerWithMostWater {

    public static int containerWithMostWater(int[] alturas) {
        int areaMax = 0;

        for (int i = 0; i < alturas.length; i++) {
            for (int j = 0; j < alturas.length; j++) {
                if (i != j) {
                    int altura = Math.min(alturas[i], alturas[j]);
                    int ancho = j - i;
                    int area = altura * ancho;

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

        return areaMax;
    }

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

Raul Navarro

student•

Mi primera solución:

function getContainerCapacity (numbers, size) {
    /* 
    T = O(n)
    S = O(1)
    */
let maxNumber = 0
let previousNumber = 0;
let capacityContainer;

for (let i = 1; i < size; i++){
    if(numbers[i] > numbers[i - 1] && numbers[i] >= maxNumber) {
        if(i <= 1){
            previousNumber = numbers[i-1];
        } else {
            previousNumber = numbers[i-1] <= previousNumber ? maxNumber : numbers[i-1];
        }
        maxNumber = numbers[i];
    } else if (numbers[i] < numbers[i - 1] && i == 1){
        maxNumber = numbers[i-1];
        previousNumber = numbers[i];
    }
    if(previousNumber != 0 && numbers[i] != maxNumber && numbers[i] > previousNumber){
        previousNumber = numbers[i];
    }
}
    capacityContainer = previousNumber * previousNumber;
    return `The capacity of this container is: ${capacityContainer} liters`; 
}

function getRandomArray (size) {
    if(typeof size != "number") return "Debes ingresar un número";
    const array = new Array(size)
    for (let i=0; i<size; i++) {
        array[i] = Math.floor(Math.random() * 100);
    }
    return array;

}

const arr = getRandomArray(10);
console.log(arr);
console.log(getContainerCapacity(arr, arr.length));