Container With Most Water @LeetCode

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.

	package leetcode;
	/**
	* Solution:for any i, The maximum area will be the farthest j that has a[j] > a[i];
	* the contain volume is decided by the shorter line.
	* Move the pointer which points to the smaller element in array.
	* Since i is lower than j, so there will be no jj < j that
	* make the area from i,jj is greater than area from i,j
	*
	* Assume a[j] > a[i1], a[i2], a[i1] < a[i2]. A(i1,j) <= A(i2,j). Could proof it through calculation.
	* So we will not miss max value even though we move forward the pointer.
	*
	* Reference: http://jane4532.blogspot.com/2013/05/container-with-most-water-leetcode.html
	* @author jeffwan
	* @date Apr 3, 2014
	*/
	public class ContainerWithMostWater {
	public static void main(String[] args) {
	int[] height = { 2,3,100,4 };
	System.out.println(maxArea(height));
	}
	// O(n)
	public static int maxArea(int[] height) {
	if (height == null || height.length == 0) {
	return 0;
	}
	int left = 0;
	int right = height.length - 1;
	int max = 0;
	while (left < right) {
	max = Math.max(max,
	(right - left) * Math.min(height[left], height[right]));
	if (height[left] < height[right]) {
	left++;
	} else {
	right--;
	}
	}
	return max;
	}
	// Brute Force -- Time Limit Exceeded O(n^2)
	public int maxArea2(int[] height) {
	if (height == null || height.length == 0) {
	return 0;
	}
	int max = Integer.MIN_VALUE;
	int minHeight = Integer.MAX_VALUE;
	for (int i = 0; i < height.length; i++) {
	for (int j = i + 1; j < height.length; j++) {
	minHeight = Math.min(height[i], height[j]);
	max = Math.max(max, minHeight * (j - i));
	System.out.println(" i " + i + " j "+ j + " max " + max);
	}
	}
	return max;
	}
	}

view raw ContainerWithMostWater.java hosted with ❤ by GitHub