11. Container With Most Water

Question

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.

Notice that you may not slant the container.

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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 2:

Input: height = [1,1]
Output: 1

Algorithm

1. This question is a typical array question using two pointers.
2. However, the two pointers moves two directions, not like single direction two pointers problem.
3. So you start from left and right side of this chart, and move to forward if this side is shorter, since we are going to the middle of this chart, the length is becoming shorter, so the height should be larger if we want to get a larger result.
4. So we move the shorter one to expect a higher one.

Code

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