Description

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

Submission 1 – Brute-force

class Solution {
public int maxArea(int[] height) {
int max = 0;
for(int i = 0; i < height.length; i++) {
for(int j = 0; j < height.length; j++) {
if(i != j) {
int area = Math.abs(i – j) * Math.min(height[i], height[j]);
max = max < area ? area : max;
}
}
}
return max;
}
}

This solution is obvious and with O(N^2) complexity in terms of time. A slow solution, but the coding is easy and solves the problem.

Submission 2 – Two Pointer Approach

The crux here is that when we have 2 pointers one at each side of the array and gradually moving towards each other, the distance between will decrease. In order to make sure that an increase in area, we should try to make the shorter boundary longer. So we move the shorter one towards the other recursively.

We

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        for(int i = 0, j = height.length - 1; i < j;) {
            int val = Math.abs(i - j) * Math.min(height[i], height[j]);
            if(val > max) {
                max = val;
            }
             
            if(height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return max;
    }
}