[LeetCode 11] Container With Most Water

Question

link

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) 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.

Stats

Frequency	2
Diffficulty	3
Adjusted Difficulty	4
Time to use	----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

Assume i and j are 2 points in x-axis where i < j. The container volume is decided by the shorter height among the two.

Assume i is lower than j, there will be no i < jj < j that makes the area of (i,jj) greater than area of (i,j). In other words, all (i,jj) is smaller than (i,j) so there’s no need to check them.

Thus we move i forward by 1. This idea is explained in this post.

Solution

Two-pointer scan. And always move the shorter board index (if we consider it to be a rectangle bucket), as explained in this post.

My code

public class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length <= 1) {
            return 0;
        }
        int left = 0;
        int right = height.length - 1;
        int area = 0;
        // start calculating area and shrinking the distance
        // between left and right pointer
        while (left < right) {
            area = Math.max(area, (right - left)
                * Math.min(height[left], height[right]));
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return area;
    }
}