Container With Most Water

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.

It is easy to come up a brute force solution that calculate area between any two vertical lines and then trace a max area. That runs out of time.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

public class Solution { public int maxArea(int[] height) { long max = Integer.MIN_VALUE; long[][] areas = new long[height.length][height.length]; for(int i=0;i<height.length;i++){ for(int j=0;j<height.length;j++){ //i==j, area=0, area is initialized as 0 so no need to compute it if(i!=j&&areas[i][j]==0){ areas[i][j]=areas[j][i]=Math.abs(i-j)*Math.min(height[i],height[j]); max = Math.max(max,areas[i][j]); } } } return (int)max; } }

Below is a better solution that start from max bottom size, then step by step, while reducing bottom size, it tries to find bigger height to hopefully find a bigger area.

This solution is easy understand but it only beats less than 2% of other submissions.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

public class Solution { public int maxArea(int[] height) { int i=0,j=height.length-1; int max = Integer.MIN_VALUE; int area = 0; while(i<j){ //i==j, area=0, area is initialized as 0 so no need to compute it area=Math.abs(i-j)*Math.min(height[i],height[j]); max = Math.max(max,area); if(height[i]<height[j])//remove shorter line to find bigger height i++; else j--; } return max; } }