About Container With Most Water in leetcode

 Today I want to discuss about "Container With Most Water" in leetcode, the problem statement as below:

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

In short, we have an array of non-negative integer, and we want to find the max of the area defined by index i and j (i,j i in range [0,n-1] inclusive), the area is calculated as:

        area = (j-i) * Math.min(height[i], height[j]) assuming j > i;

There're couple of algorithms that can tackle this problem, the naive one is the brute force that loop over all pairs of (i,j) and compute the area, then pick the biggest one.

let maxArea = 0;

for(let i = 0; i < n; i++) {

    for(let j = i + 1; j < n; j++) {

         const area = (j - i) * Math.min(height[i], height[j]);

         maxArea = Math.max(area, maxArea);

    }

} 

This algorithm will work just fine, however, the time complexity of this algorithm is O(n^2), which is not a good one.

Dig deeper into the problem statement, we can see that there're 2 factors impact on the area, one is the distance between 2 indexes, so, naturally we will try to start with the left most and right most index in array, and then narrow down the range until left index becomes right index. In each step, we will use invariant by choosing the side which have the smaller height, and moving the pointer on that size.

    let maxWater = 0;

    let left = 0, right = n- 1;

    while(left < right){

        let waterAtLR = (right-left)* Math.min(height[left], height[right]);

        maxWater = Math.max(maxWater, waterAtLR);

        if(height[left] <= height[right]){

            left++;

        } else {

            right--;

        }

    }

This algorithm only has  O(n) time complexity and still have O(1) space complexity.

Let's prove the correctness of this invariant (heuristic) by proving the while loop will visit the maximum pair.

Assuming there's a pair of index (i,j) with i < j having the max area possible. And also in the while loop, either left or right point will move, so let's assuming left index will hit i first (in case right index hits j first, the proof would be similar).

So, in this case, we have left = i, and right > j. We will prove that the in the loop, only the right index will move till it hits j while the left index will stay at i.

To prove this, assuming we have the contradiction that instead of the right index moves, the left index does for some right index > j. So, looks into the if condition, in this case we have:

height[i]  <= height[right]; 

Let's compute the area making by i, right in this case, we have:

area = (right - i) * Math.min(heigth[i], height[right]) 

=> area = (right - i) * height[i] as height[right] > height[i]

=> area > (right - i) * Math.min(height[i], height[j]) 

=> area > (j - i ) *  Math.min(height[i], height[j])  as right > j

=> area > maxArea

The last statement contradicts with our initial assumption that the area made by index (i,j) is the maximum one, hence prove the correctness of this algorithm.

Happy coding.