Problem
Given an integer array height, where each element represents the height of a vertical line, find two lines that together with the x-axis form a container capable of holding the maximum amount of water.Return the maximum amount of water the container can store.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
height = [1,8,6,2,5,4,8,3,7] Output
49 Solution
This solution uses the Two Pointer technique to find the maximum area efficiently.One pointer starts at the beginning of the array, while the other starts at the end. The amount of water that can be stored is determined by the shorter of the two heights multiplied by the distance between them.
After calculating the current area, the pointer pointing to the shorter line is moved inward. Moving the taller line cannot increase the area because the shorter line still limits the container's height.
During the traversal, the maximum area encountered is continuously updated and returned as the answer.
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while (left < right) {
int width = right - left;
int currentArea = Math.min(height[left], height[right]) * width;
// Update the maximum area.
maxArea = Math.max(maxArea, currentArea);
// Move the shorter line.
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
Complexity
The algorithm traverses the array using two pointers. Since each pointer moves only toward the center, the overall time complexity isO(n).
Only a few variables are used to store the pointers and the maximum area, so the extra space complexity is
O(1).