Container With Most Water

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.

Approach

Let’s recall some basic math first.
Area of Rectangle = Base * Height
Here, the height is the minimum of both pillars (since it’ll spill over at the minimum). The base is the distance between the pillars.

Brute Force Approach
This is the easy approach, but at O(N^2) time complexity, we could likely do better. In this approach we have a loop within a loop, and we simply check every combination of pillar.
Note that the inner loop starts at i+1. This is for two reasons. Firstly, we don’t want to re-use the same pillar. The rules don’t explicit prevent this but it’ll be zero volume since the base is zero. Also, there’s no difference between what’s pillar 1 and pillar 2. Therefore we only need to check each combination once.

var maxArea = function(height) {
    let max=0;
    for (let i=0;i<height.length;i++) {
        for (let j=i+1;j<height.length;j++) {
            const area=(j-i)*Math.min(height[i],height[j]);
            if (area>max) {
                max=area;
            }
        }
    }
    return max;
};

Two Pointer Approach

How can we improve the solution? Well, the question is do we need to check every combination?

The approach initially detailed, of looking at the formula of area and looking at the drivers that maximizes that, is still relevant here. If we are wider, we get more area. If we are taller, we get more area. The height is the lower of the two pillars.

We start at the ends, since that maximizes the width. As the height is the lower of the two pillars, we consider looking at a closer pillar if it adds to the height. Moving inwards from the taller pillar would not add to the area since it is limited by the shorter pillar, we’d just be losing width.

In other words, this has the feel of a greedy algorithm. We look at maximizing for each step we take.

var maxArea = function(height) {
    let area=0;
    let j=height.length-1;
    let i=0;
    let maxArea=area=(j-i)*Math.min(height[i],height[j]);
    while (j>i) {
        //console.log("Checking ",i,j)
        //move closer from side with lower
        if (height[i]>height[j]) {
            j--;
        }
        else {
            i++;
        }
        const area=(j-i)*Math.min(height[i],height[j]);
        //if we don't need to know which pillar is used
        maxArea=Math.max(area,maxArea);
    }
    return maxArea;
};