Question
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.
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;
}
}