📚 Table of Contents
📋 Problem Statement
Two lines at indices i and j hold water with area:
min(height[i], height[j]) * (j - i).
Find the maximum possible area.
Examples
Input: height = [1,8,6,2,5,4,8,3,7]Output: 49Best pair is indices 1 and 8: min(8,7) * (8-1) = 7 * 7 = 49.
Input: height = [1,1]Output: 1Only one container possible.
Constraints
2 <= height.length <= 10^50 <= height[i] <= 10^4
🎯 Real-World Analogy
Sliding Fence Posts Across a Field
You are choosing two fence posts to stretch a tarp between them. The tarp height is limited by the shorter post, and width is the distance between posts.
If you keep the shorter post and move the taller one inward, width shrinks and limiting height does not improve. So that move cannot produce a better area.
The only potentially useful move is to drop the shorter boundary and hope to find a taller one, even though width decreases.
💡 Key Insights
- Area is constrained by the shorter of two heights.
- Start with widest container: pointers at both ends.
- Moving the taller pointer cannot increase limiting height and always loses width.
- Move only the shorter pointer each step.
- This gives an O(N) scan with complete coverage of useful candidates.
💻 Solution Approaches
Approach 1: Brute Force
Time: O(N²) | Space: O(1)
Evaluate every pair (i, j), compute area, keep maximum.
Correct but too slow for large inputs.
Approach 2: Two Pointers (Recommended)
Time: O(N) | Space: O(1)
Track left and right boundaries. Compute area, then move the pointer at the shorter line.
Python Implementation
from typing import List
def max_area(height: List[int]) -> int:
"""
Two-pointer solution for maximum container area.
Time: O(N)
Space: O(1)
"""
left = 0
right = len(height) - 1
best = 0
while left < right:
width = right - left
h = min(height[left], height[right])
area = h * width
if area > best:
best = area
# Move the limiting side.
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
JavaScript Implementation
function maxArea(height) {
/**
* Two-pointer solution for maximum container area.
*
* Time: O(N)
* Space: O(1)
*/
let left = 0;
let right = height.length - 1;
let best = 0;
while (left < right) {
const width = right - left;
const h = Math.min(height[left], height[right]);
const area = h * width;
if (area > best) {
best = area;
}
// Move the limiting side.
if (height[left] < height[right]) {
left += 1;
} else {
right -= 1;
}
}
return best;
}
🔍 Step-by-Step Walkthrough
Trace height = [1,8,6,2,5,4,8,3,7]:
⚡ Complexity Analysis
Time Complexity: O(N)
- Single sweep: each pointer moves inward at most N-1 times.
- Per step: constant-time arithmetic and comparisons.
- Total: linear in number of heights.
Space Complexity: O(1)
- No auxiliary arrays: only indices and running best.
- Input reused in-place: read-only scan.
🔧 Edge Cases
- Minimum size array of length 2
- All zeros -> area 0
- Strictly increasing or decreasing heights
- Multiple pairs producing same max area
- Very large N where O(N²) times out
🧪 Test Cases
Python
def test_max_area():
assert max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
assert max_area([1, 1]) == 1
assert max_area([4, 3, 2, 1, 4]) == 16
assert max_area([1, 2, 1]) == 2
assert max_area([0, 0, 0, 0]) == 0
print("✅ all tests passed")
JavaScript
function testMaxArea() {
console.assert(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) === 49, "test 1");
console.assert(maxArea([1, 1]) === 1, "test 2");
console.assert(maxArea([4, 3, 2, 1, 4]) === 16, "test 3");
console.assert(maxArea([1, 2, 1]) === 2, "test 4");
console.assert(maxArea([0, 0, 0, 0]) === 0, "test 5");
console.log("✅ all tests passed");
}
💼 Interview Tips
- Write area formula first:
min(h[i], h[j]) * (j-i). - Justify pointer movement with elimination argument.
- Explain why moving taller side is never helpful.
- State O(N²) brute force first, then optimize to O(N).
- Mention this same pattern appears in trapping/water style pointer problems.
🎓 Key Takeaways
- Two-pointer correctness comes from proving safe eliminations.
- When width shrinks every step, improve the limiting height side.
- This pattern is a high-frequency interview optimization path.