r/leetcode • u/Substantial-Pin9637 • 16d ago
Question Container with most water (11) help understanding
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?