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 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

 

 

Solution:

Two pointers approach.

The left pointer starts from the beginning of the input array, the right pointer starts from the end.

Memorizing the maxArea.

Moving the pointer which holes smaller value, so that we have a chance to get a larger maxArea.

 

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

 

Time complexity : $O(n)$.

Space complexity : O(1).