Container With Most Water — Two-Pointer Contraction
Hold both ends of the array and always move the shorter wall inward to maximise trapped area in one pass.
Problem Statement
Given an array of non-negative heights, choose two lines that, together with the x-axis, form a container holding the most water.
Why This Problem Matters
- Builds intuition for two-pointer contraction on monotonic metrics such as width × height.
- Teaches you to reason why certain moves (shrinking the taller wall) can never improve the answer.
- Interviewers use it to test greedy reasoning and proof-by-contradiction skills.
Thought Process
Start with brute force
Checking every pair of lines is O(n^2); that is fine for reasoning but fails on input sizes up to 10^5.
Observe what controls area
Area = width × min(height[left], height[right]); only the shorter wall limits the fill level.
Decide which pointer to move
Moving the taller wall can only shrink width without increasing height, so always advance the shorter wall.
Maintain a running maximum
Compare each candidate area with the best so far before adjusting pointers.
Step-by-Step Reasoning
- Initialise left = 0, right = n - 1, best = 0.
- Compute width = right - left and height = min(heights[left], heights[right]).
- Update best with width × height.
- Move the pointer at the shorter wall inward and repeat until the pointers cross.
Dry Run
left = 0, right = 8, height = 1
Area is 8, best = 8; advance left because height[0] < height[8].
left = 1, right = 8, height = 7
Area becomes 49, best updates to 49; move right pointer to hunt for taller walls.
Complexity Analysis
Time
O(n)
Space
O(1)
Why
Each pointer moves at most n steps while we maintain constant extra state.
Annotated Solution
public class ContainerWithMostWater {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int best = 0;
while (left < right) {
int width = right - left;
int minHeight = Math.min(height[left], height[right]);
best = Math.max(best, width * minHeight);
if (height[left] < height[right]) {
left += 1;
} else {
right -= 1;
}
}
return best;
}
}The shorter side limits the fill level, so only it is worth moving. Each contraction either keeps the height the same or finds a taller wall, all while width shrinks by one.
Common Pitfalls
- Moving the taller wall first can never increase area and wastes work.
- Forgetting to recompute width after pointer moves leads to stale calculations.
- Confusing height comparisons with index comparisons produces negative widths.
Follow-Up Questions
- How would the strategy change if the heights could be negative (representing trenches)?
- Can you prove the two-pointer strategy optimal via contradiction to an interviewer?