Learning Journal

2/16/2024

Container With Most Water

function maxArea(height: number[]): number {
    let left = 0, right = height.length - 1,
        maxVol = 0;

    while(left !== right) {
        
        const curVol = Math.min(height[left], height[right]) * (right - left);
        if(curVol > maxVol)
            maxVol = curVol;
    
        if(height[left] < height[right]){
            left++;
        }
        else {
            right--;
        }

    }
    
    return maxVol;
};function maxArea(height: number[]): number {
    let left = 0, right = height.length - 1,
        maxVol = 0;

    while(left !== right) {
        
        const curVol = Math.min(height[left], height[right]) * (right - left);
        if(curVol > maxVol)
            maxVol = curVol;
    
        if(height[left] < height[right]){
            left++;
        }
        else {
            right--;
        }

    }
    
    return maxVol;
};

THE PROBLEM

The solution is simple. The difficult thing is to convince yourself that it arrives at the correct result.

Let's suppose that the result we found is not the maxVol. So, there must be some different combination of left and right that is the result. Let's say that they are left_1 and right_1.

Notice that the algorithm only stops when left meets right. But, they can't both cross left_1 and right_1, Otherwise, the maxVol will be of left_1 and right_1. So, either left crosses left_1 or right crosses right_1.

So if left crosses left_1, right must be somewhere after right_1 and all heights from left to right must be less than right. It can't be because right_1 is greater than right.

The same thing with if right crosses right_1, left must be somewhere before left_1 and all height from left to right must be less than left. It can't be true because left_1 is greater than left.

Revised by ChatGPT

The solution is straightforward, but the challenge lies in convincing oneself that it yields the correct result.

Suppose the result we found is not the maximum volume (maxVol). In that case, there must be a different combination of left and right that yields the actual maximum volume. Let's call them left_1 and right_1.

Observe that the algorithm only stops when left meets right. However, both left and right cannot simultaneously cross left_1 and right_1; otherwise, maxVol would be the volume formed by left_1 and right_1. Thus, either left crosses left_1 or right crosses right_1.

If left crosses left_1, then right must be positioned after right_1, and all heights from left to right must be less than or equal to the height at right. This scenario is impossible because the height at right_1 is greater than the height at right.

Similarly, if right crosses right_1, then left must be positioned before left_1, and all heights from left to right must be less than or equal to the height at left. This scenario is also impossible because the height at left_1 is greater than the height at left.

Therefore, the algorithm does indeed find the maximum volume.