Container With Most Water

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.

 

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

 

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

The O(n) solution with proof by contradiction doesn't look 
 enough to me. Before moving on, read any example of the 
 algorithm first if you don't know it yet.

Here's another way to see what happens in a matrix representation:

Draw a matrix where rows correspond to the position of the left 
line, and columns corresponds to the position of the right line.

For example, say n=6. Element at (2,4) would corresponds to 
the case where the left line is at position 2 and the right 
line is at position 4. The value of the element is the volume
 for the case.

In the figures below, x means we don't need to compute the 
volume for that case, because:

on the diagonal, the two lines are overlapped;
the lower left triangle area of the matrix, the two lines are
 switched and the case is symmetric to the upper right area.
We start by computing the volume at (1,6), denoted by o. Now 
if the left line is shorter than the right line, then moving 
the right line towards left would only decrease the volume, so
 all the elements left to (1,6) on the first row have smaller 
 volume. Therefore, we don't need to compute those cases (crossed by ---).

  1 2 3 4 5 6
1 x ------- o
2 x x
3 x x x 
4 x x x x
5 x x x x x
6 x x x x x x
So we can only move the left line towards right to 2 and compute (2,6). 
Now if the right line is shorter, all cases below (2,6) are eliminated.

  1 2 3 4 5 6
1 x ------- o
2 x x       o
3 x x x     |
4 x x x x   |
5 x x x x x |
6 x x x x x x
And no matter how this o path goes, we end up only need to find the max 
value on this path, which contains n-1 cases.

  1 2 3 4 5 6
1 x ------- o
2 x x - o o o
3 x x x o | |
4 x x x x | |
5 x x x x x |
6 x x x x x x
Hope this helps. I feel more comfortable seeing things this way.

C++

The intuition behind this approach is that the area formed between the lines will always be limited by the height of the shorter line. Further, the farther the lines, the more will be the area obtained.

We take two pointers, one at the beginning and one at the end of the array constituting the length of the lines. Father, we maintain a variable $\text{maxarea}$ to store the maximum area obtained till now. At every step, we find out the area formed between them, update $\text{maxarea}$ and move the pointer pointing to the shorter line towards the other end by one step.

The algorithm can be better understood by looking at the example below:class Solution {
public:
    int maxArea(vector<int>& height) {
        
       int n=height.size(),maxv=INT_MIN,tmp;
        int i=0,j=n-1;
       while(i<j)
       { 
                tmp=(j-i)*(min(height[i],height[j]));
                maxv=max(maxv,tmp);
           if(height[i]<height[j])
               ++i;
           else
               --j;
        }
        
        return maxv;
    }
};

JAVA

public class Solution {
    public int maxArea(int[] height) {
        int maxarea = 0;
        for (int i = 0; i < height.length; i++)
            for (int j = i + 1; j < height.length; j++)
           maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i));
        return maxarea;
    }
}

public class Solution {
    public int maxArea(int[] height) {
        int maxarea = 0, l = 0, r = height.length - 1;
        while (l < r) {
         maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));
            if (height[l] < height[r])
                l++;
            else
                r--;
        }
        return maxarea;
    }
}

PYTHON

If height[L] < height[R], move L, else move R. Say height[0] < height[5],
 area of (0, 4), (0, 3), (0, 2), (0, 1) will be smaller than (0, 5), 
 so no need to try them.

def maxArea(self, height):
    L, R, width, res = 0, len(height) - 1, len(height) - 1, 0
    for w in range(width, 0, -1):
        if height[L] < height[R]:
            res, L = max(res, height[L] * w), L + 1
        else:
            res, R = max(res, height[R] * w), R - 1
    return res