A complete visual walkthrough of the two-pointer approach — from brute force to the optimal O(n) solution.
Given an array of heights, each pair of lines forms a container. The area of water it can hold is min(height[i], height[j]) * (j - i). The naive approach checks every pair.
// Brute Force: O(n^2) — check every pair for (int i = 0; i < height.length; i++) for (int j = i + 1; j < height.length; j++) maxArea = Math.max(maxArea, Math.min(height[i], height[j]) * (j - i));
With n lines there are n*(n-1)/2 pairs to check, giving O(n2) time. For large inputs (n up to 100,000) this is far too slow. Can we do better?
Start with the widest possible container by placing one pointer at each end. The width is maximized, so the only way to find a larger area is to find a taller minimum height.
The area is limited by the shorter line. Moving the taller line inward would:
So moving the taller line guarantees a smaller or equal area. But moving the shorter line might reveal a taller line, potentially increasing the area despite the narrower width.
The greedy argument: By always moving the shorter line, we never skip a potential maximum. Every pair where the shorter line was the bottleneck is provably worse than what we already computed with the wider width.
Let us trace through the full example height = [1, 8, 6, 2, 5, 4, 8, 3, 7] step by step. At each step we calculate the area, update our maximum, and move the shorter pointer inward.
h[0]=1, h[8]=7. Area = min(1,7) * (8-0) = 1 * 8 = 8. Max = 8.
h[L] < h[R] → move L right to 1.
h[1]=8, h[8]=7. Area = min(8,7) * (8-1) = 7 * 7 = 49. Max = 49.
h[L] > h[R] → move R left to 7.
h[1]=8, h[7]=3. Area = min(8,3) * (7-1) = 3 * 6 = 18. Max = 49.
h[L] > h[R] → move R left to 6.
h[1]=8, h[6]=8. Area = min(8,8) * (6-1) = 8 * 5 = 40. Max = 49.
h[L] = h[R] → move R left to 5 (either works, we choose right).
h[1]=8, h[5]=4. Area = min(8,4) * (5-1) = 4 * 4 = 16. Max = 49.
h[L] > h[R] → move R left to 4.
h[1]=8, h[4]=5. Area = min(8,5) * (4-1) = 5 * 3 = 15. Max = 49.
h[L] > h[R] → move R left to 3.
h[1]=8, h[3]=2. Area = min(8,2) * (3-1) = 2 * 2 = 4. Max = 49.
h[L] > h[R] → move R left to 2.
h[1]=8, h[2]=6. Area = min(8,6) * (2-1) = 6 * 1 = 6. Max = 49.
h[L] > h[R] → move R left to 1. Now L = R, loop ends.
Only 8 iterations instead of 36 pairs. The two-pointer approach examines at most n-1 pairs because each step moves one pointer inward, and the pointers can only meet once.
These boundary scenarios test the robustness of the two-pointer solution.
[1, 1] → Area = min(1,1) * 1 = 1. The algorithm runs exactly one iteration. This is the minimum valid input (n ≥ 2).
[5, 5, 5, 5] → Area = 5 * 3 = 15. The widest container is always best since all heights are equal. First pair checked wins.
[1, 2, 3, 4, 5] → Area = 6. The left pointer keeps moving right since it is always shorter. Best pair is (1,4) with min(2,5)*3=6.
[1, 1, 1, 100, 1, 1, 1] → Area = 6. The tall bar is never the bottleneck. The area is limited by the shorter lines on either side.
No special-case code needed. The two-pointer approach handles all these cases naturally. The while loop condition left < right ensures we always have two distinct lines.
class Solution { public int maxArea(int[] height) { // Start with widest possible container int left = 0, right = height.length - 1; int maxArea = 0; while (left < right) { // Water level is limited by the shorter line int h = Math.min(height[left], height[right]); int w = right - left; // Update maximum area maxArea = Math.max(maxArea, h * w); // Move the pointer at the shorter line inward // Moving the taller line can never increase area if (height[left] < height[right]) left++; // left is shorter, try a taller one else right--; // right is shorter (or equal), try a taller one } return maxArea; } }
Enter a comma-separated list of heights and step through the two-pointer algorithm visually.
Each iteration moves one pointer inward, so the two pointers together traverse the array exactly once (n - 1 steps in the worst case). Each step performs O(1) work: one comparison, one multiplication, one max update. No additional data structures are needed beyond three integer variables.
Why is this optimal? Any algorithm must read all n heights at least once (an adversary can hide the answer at any position), so O(n) is a lower bound. The two-pointer approach matches this bound exactly.