Container With Most Water

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.

Naive Solution

A simple way to do it is to go through the height array, calculate possible volumes for the current height together with all other heights, and find the maximum.

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

It is easy to implement. But since it calculates all possible combinations, it takes time O(n^2).

Fast Solution

There are two factors deciding the volume of a container: width and height. So, if we starts from the two ends of the array and moves towards middle, the only bottleneck would be the height.

We can apply greedy strategy as follows:
We always move the shorter boundary of the two. By moving the shorter one, we may arrive at a higher boundary so as to get a greater volume (although width decreased); it is not necessary to move the higher one since no matter if the next height is greater or smaller, it won’t change the volume — the shorter boundary is the limit for a container.

public int maxArea(int[] height) {
	int len = height.length, low = 0, high = len - 1;
	int maxArea = 0;
	while (low < high) {
		maxArea = Math.max(maxArea,
				(high - low) * Math.min(height[low], height[high]));
		if (height[low] < height[high]) {
			low++;
		} else {
			high--;
		}
	}
	return maxArea;
}