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 that holds the most water.
Return the maximum amount of water a container can store.
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: Lines at indices 1 and 8 (values 8 and 7). Width = 7, height = min(8,7) = 7. Area = 49.
Input: height = [1,1]
Output: 1
Constraints:
- n == height.length
- 2 <= n <= 105
- 0 <= height[i] <= 104
Contents
- Approach 1 — Brute Force O(n²)
- Approach 2 — Two Pointers O(n)
- Complexity Analysis
Brute Force O(n²)
Try every pair of lines and compute the contained area.
public int maxArea(int[] height) {
int max = 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]);
max = Math.max(max, area);
}
}
return max;
}
Two Pointers O(n)
Key insight: Area = width × min(height[left], height[right]).
Width decreases as we move pointers inward. To maximise area we must try to increase height —
so we always move the pointer pointing at the shorter line.
Why? Moving the taller line inward can only decrease or maintain width while the height is still
limited by the shorter line. So moving the shorter line gives a chance to find a taller one.
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxWater = 0;
while (left < right) {
int width = right - left;
int minH = Math.min(height[left], height[right]);
maxWater = Math.max(maxWater, width * minH);
// Move the shorter line inward
if (height[left] <= height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}
| Approach | Time | Space |
|---|
| Brute Force | O(n²) | O(1) |
| Two Pointers | O(n) | O(1) |