Approach Summary
Start with widest container. Move the pointer with the shorter height inward — the wider pointer cannot improve the container area.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Brute Force (All Pairs) | O(n²) | O(1) | Compute the water area between every pair of lines (i, j) with i < j. |
| 2 Approach 2: Two Pointers Shrinking Inward (Optimal) | O(n) | O(1) | Start at maximum width and move the pointer pointing to the shorter vertical bar inward. |
Approach 1: Brute Force (All Pairs)
Use two nested loops to check every possible pair of lines. For each pair i and j, calculate `(j - i) * min(height[i], height[j])` and record the maximum area. For n = 10⁵, quadratic comparisons cause Time Limit Exceeded.
Approach 1: Brute Force (All Pairs) Implementation
Approach 1: Brute Force (All Pairs)
class Solution {
public int maxArea(int[] height) {
int maxWater = 0;
for (int i = 0; i < height.length; i++) {
for (int j = i + 1; j < height.length; j++) {
int area = (j - i) * Math.min(height[i], height[j]);
maxWater = Math.max(maxWater, area);
}
}
return maxWater;
}
}class Solution {
public:
int maxArea(vector<int>& height) {
int maxWater = 0;
int n = height.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int area = (j - i) * min(height[i], height[j]);
maxWater = max(maxWater, area);
}
}
return maxWater;
}
};def max_area(height: list[int]) -> int:
max_water = 0
n = len(height)
for i in range(n):
for j in range(i + 1, n):
area = (j - i) * min(height[i], height[j])
max_water = max(max_water, area)
return max_waterfunction maxArea(height) {
let maxWater = 0;
const n = height.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
const area = (j - i) * Math.min(height[i], height[j]);
maxWater = Math.max(maxWater, area);
}
}
return maxWater;
}Approach 2: Two Pointers Shrinking Inward (Optimal)
Place pointer `left = 0` and pointer `right = n - 1`. The area is constrained by `min(height[left], height[right])`. If `height[left] < height[right]`, moving `right` inward cannot increase the area because width decreases and the height limit is still bounded by `height[left]`. The only possibility of discovering a larger area is finding a taller line by moving `left` inward. Greedily advancing the shorter line guarantees that no potential maximum area is skipped.
Approach 2: Two Pointers Shrinking Inward (Optimal) Implementation
Approach 2: Two Pointers Shrinking Inward (Optimal)
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxWater = 0;
while (left <= right) {
if (height[left] > height[right]) {
maxWater = Math.max(maxWater, (right - left) * height[right]);
right--;
} else {
maxWater = Math.max(maxWater, (right - left) * height[left]);
left++;
}
}
return maxWater;
}
}class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int maxWater = 0;
while (left <= right) {
if (height[left] > height[right]) {
maxWater = max(maxWater, (right - left) * height[right]);
right--;
} else {
maxWater = max(maxWater, (right - left) * height[left]);
left++;
}
}
return maxWater;
}
};def max_area(height: list[int]) -> int:
left, right = 0, len(height) - 1
max_water = 0
while left < right:
width = right - left
if height[left] > height[right]:
max_water = max(max_water, width * height[right])
right -= 1
else:
max_water = max(max_water, width * height[left])
left += 1
return max_waterfunction maxArea(height) {
let left = 0;
let right = height.length - 1;
let maxWater = 0;
while (left < right) {
const width = right - left;
if (height[left] > height[right]) {
maxWater = Math.max(maxWater, width * height[right]);
right--;
} else {
maxWater = Math.max(maxWater, width * height[left]);
left++;
}
}
return maxWater;
}Edge Cases to Watch
- Two lines array (minimum constraint)
- All lines having the identical height
- Tallest lines separated by short lines in the middle
- One extremely tall line and all others very short
Master the Two Pointers Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Two Pointers pattern.
How to Recognize This Pattern
- Max area between two heights
- Pointer convergence
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)