Problem

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Examples

Example 1:

Input:
height = [1,8,6,2,5,4,8,3,7]
Output:
 49
Explanation: 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 2:

Input : [1, 5, 4, 3]
Output : 6

Explanation : 5 and 3 are distance 2 apart. So size of the base = 2. Height of container = min(5, 3) = 3.
So total area = 3 * 2 = 6

Solution

Method 1 - Naive

One straightforward method is to iterate through the height array, compute the potential volumes combining the current height with all other heights, and then identify the maximum value.

Code

Java
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]);
			maxArea = Math.max(maxArea, area);
		}
	}
	return maxArea;
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Using Two Pointers

The volume of a container is determined by two factors: width and height. By starting from both ends of the array and moving towards the middle, height becomes the limiting factor.

Initially, assume the result is 0 and scan the array from both ends. If the left height is less than the right height, move the left pointer rightwards to find a higher value. Conversely, if the left height is greater than the right height, move the right pointer leftwards to find a higher value. Throughout the process, continually track the maximum value.

Code

Java
public int maxArea(int[] height) {
	if (height == null || height.length<2) {
		return 0;
	}

	int max = 0;
	int left = 0;
	int right = height.length - 1;

	while (left<right) {
		int area = (right - left) * Math.min(height[left], height[right]);
		max = Math.max(max, area);
		if (height[left]<height[right])
			left++;
		else
			right--;
	}

	return max;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)