Cálculo Óptimo de Área en Listas de Alturas

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.

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