[LeetCode] 11. Container With Most Water

Posted on | In

Problem

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. 11. Container With Most Wateruestion

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:

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

Explanation

  1. We calculate the area by multipling the x-axis with the height, specifically the min height between the two bar.

  2. When two bars at the beginning and at the end, the x-axis is the largest. So, we starts from here and use two pointers technique. We first calcualte the area with two bar at both end, then compare those two bars. If the left bar is shorter, we move it to the next bar, and compute the area. Else, if the right bar is shorter, then we move it to the previous bar and compute the area. Until the left pointer is greater or equal to the right pointer, we break out and return the maximum area.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        int left = 0;
        int right = height.length-1;
        while (left < right) {
            int area = (right-left)*Math.min(height[left], height[right]);
            max = Math.max(max, area);
            if (height[left] < height[right]) {
                left += 1;
            } else {
                right -= 1;
            }
        }
        return max;
    }
}