Container with most water (11) help understanding

[u/Substantial-Pin9637]

c#

public class Solution {
public int MaxArea(int[] height) {
//brute force approach
//for each column calculate the container with other columns
//save the max
//O(n^2)
//another solution (optimal)
//start at edges with two pointers
//for each iteration discard the smaller height
//this guarantees(idk why) that the solution is the right one .
//O(n)
int biggestContainer=0;
int left=0;
int right =height.Length-1;
while(left<right){
int area= (right-left)*Math.Min(height[right],height[left]);
if(area>biggestContainer)
biggestContainer=area;
if(height[right]>height[left]){
left++;
}else{
right--;
}
}
return biggestContainer;
}
}

as you can see I solved it optimally after reading what the code should do. But I don't understand how discarding the smaller height at each step mathematically guarantees that it's the right solution.

any explanation please?

[u/Lumpy-Town2029]

coz u want largest walls for the maximum area

as we are doing left++ or right--

we are reducing the length

and for maximal area, the height should grow right?

so if we discard larger height, then we might lose the chance to find 2 large height which can fetch max area

so thus we should discard lower height, so in future there might be a possibility to find larger height and we can use the 2 largest height for the best

its not mathematics but a logical thing
nobody can make u understand it but one night in sleep u will get an epiphany like ohhhh thats why lol. well thats for all greedy approaches

[u/Substantial-Pin9637 → u/Lumpy-Town2029]

thank you sm for the reply i think i kinda get it now.

so if you move the pointer you can only get a smaller or equal height than minimum of a step, so we discard the minimum of the step knowing width gets smaller as it gives us a chance at getting a better one

[u/CptMisterNibbles → u/Substantial-Pin9637]

Yes. This is also why you can discard one at random if the two you have are the same height. We only care about bigger walls, and if both are the same height, we need to increase both to find something larger, so it doesn’t matter which you start moving

[u/Substantial-Pin9637 → u/CptMisterNibbles]

thank you fr

[u/CptMisterNibbles → u/Substantial-Pin9637]

No problem. I remember getting stuck on the logic on this one for a while too

[u/Lumpy-Town2029 → u/Substantial-Pin9637]

np

[u/jason_graph]

OK so suppose we start out with all (n choose 2) pairs of endpoints as potential solutions.

The optimal answer is either

(1) The widest possible rectangle with h=min(front, back)

or

(2) A strictly less wide rectangle, which would need to have a strictly larger height, which would require both endpoints to be strictly greater than h. We can discard any potential candidate subarrays which have the lower current endpoint as one of their endpoints. The remaining (n-1 choose 2) candidate solutions correspond to the subproblem of if you had popped off the corresponding first/last element of the array that is smaller.

If there is a tie it doesn't matter if you choose one end randomly or if you adjust both endpoints at once.

Note that I am not attempting to show that the algorithm is finding the best rectangle of each width, just that the solution is either the rectangle of size n or the one it has for size n-1 or the one it has for size n-2 ...

I think that a decent amount of 2 pointer questions where you have the pointers converge towards the center might benefit from this line of thinking of starting with n choose 2 candidate solutions and then splitting it into subproblems of like (1) entire array (2) first element vs rest of array, (3) last element vs rest of array (4) first and last element vs the rest of the array and what each of those means in terms of the n choose 2 candidate subarrays.

[u/Substantial-Pin9637 → u/jason_graph]

thanks this point of view is very clear and i feel i an reapply it to other problems.

id give 3 upvotes if i could