Container With Most Water - Equal Heights Case
The Question
When height[left] == height[right], why does moving either pointer work?
At first glance, it seems counterintuitive - shouldn’t there be a “correct” choice?
The Key Insight
When both heights are equal, moving either pointer has the same potential for improvement.
Current State
height[left] = height[right] = h
current_area = h × width
Both sides are equally limiting - the water level is determined by h on both sides.
After Moving Left Pointer
new_area = min(height[left+1], height[right]) × (width - 1)
= min(height[left+1], h) × (width - 1)
This improves only if height[left+1] > h
After Moving Right Pointer
new_area = min(height[left], height[right-1]) × (width - 1)
= min(h, height[right-1]) × (width - 1)
This improves only if height[right-1] > h
Why Either Works
Since both sides have height h, we have equal probability of finding a better solution by moving either direction.
Key reasoning:
- We’ve already lost 1 unit of width (unavoidable)
- To improve, we need to find a height > h
- We don’t know which direction has a taller line
- Since both sides are equally limiting, the choice doesn’t matter
Example Walkthrough
Height: [3, 7, 3, 5, 3]
Index: 0 1 2 3 4
Step 1: left=0, right=4
height[0] = 3, height[4] = 3 ← EQUAL!
area = min(3, 3) × 4 = 12
Scenario A: Move left pointer
Step 2a: left=1, right=4
height[1] = 7, height[4] = 3
area = min(7, 3) × 3 = 9
Found taller line (7), but still limited by right side (3)
Scenario B: Move right pointer
Step 2b: left=0, right=3
height[0] = 3, height[3] = 5
area = min(3, 5) × 3 = 9
Found taller line (5), but still limited by left side (3)
Both give area = 9. Neither is better!
The Real Reason It’s Not Counterintuitive
Think about it this way:
When heights are equal, BOTH sides are the bottleneck.
Moving either pointer:
- ✅ Explores new possibilities
- ✅ Breaks the symmetry
- ✅ Progresses toward a solution
Not moving would mean:
- ❌ Infinite loop (algorithm gets stuck)
- ❌ Miss potential better solutions
What If We Always Move Left?
if (height[left] < height[right]) {
left++;
} else { // Includes equal case
right--;
}This works! We’ll explore all meaningful combinations.
What If We Always Move Right?
if (height[left] <= height[right]) { // Note: <=
left++;
} else {
right--;
}This also works! Different exploration order, same result.
Proof That Order Doesn’t Matter (Equal Case)
Claim: When heights are equal, both pointers will eventually need to move anyway.
Proof by example:
heights = [3, 5, 3]
L R (both = 3)
Scenario 1: Move left first
[3, 5, 3]
L R → area = min(5,3) × 1 = 3
Move right: optimal solution explored ✓
Scenario 2: Move right first
[3, 5, 3]
L R → area = min(3,5) × 1 = 3
Move left: optimal solution explored ✓
Both paths explore the same middle element (5), just in different order.
Mathematical Intuition
When height[left] = height[right] = h:
Maximum possible area from here = h × (width - 1)
This maximum is achieved only if:
- The next line we encounter is ≥ h
Since we don’t know the future, and both sides are equally limiting, the choice is arbitrary.
Decision Tree
height[left] vs height[right]
│
├─ left < right → Move left (clear choice)
│ Left is bottleneck, no hope for improvement
│
├─ left > right → Move right (clear choice)
│ Right is bottleneck, no hope for improvement
│
└─ left = right → Move either (arbitrary choice)
Both are bottleneck, equal potential
Common Follow-Up: Does Moving Both Help?
No! Moving both pointers would be wasteful:
// Bad idea:
if (height[left] == height[right]) {
left++;
right--; // Skips width check!
}Why bad?
- We skip checking the area at
width - 1 - Might miss the optimal solution
- Example:
[1, 1, 100]- we’d skip the middle element!
The Correct Mental Model
When heights are equal:
- We’re at a “fork in the road”
- Either path might lead to treasure
- We pick one (doesn’t matter which)
- Continue with normal logic
The algorithm doesn’t need special handling - just pick a consistent tiebreaker (usually move left or move right).
Implementation Variations
Version 1: Move left on equal (most common)
if (height[left] < height[right]) {
left++;
} else {
right--;
}Version 2: Move right on equal
if (height[left] <= height[right]) {
left++;
} else {
right--;
}Version 3: Explicit handling (clearer but redundant)
if (height[left] < height[right]) {
left++;
} else if (height[left] > height[right]) {
right--;
} else { // Equal case
left++; // Arbitrary choice
}All three are correct and produce the same maximum area.
Key Takeaway
When heights are equal:
- Both sides are equally limiting
- Moving either explores new territory
- The choice is arbitrary (just pick one consistently)
- Don’t overthink it - the algorithm guarantees we find the maximum
The counterintuitive feeling comes from thinking there’s a “right” choice. But when both sides are equal, there truly isn’t - it’s a symmetric situation, and symmetry means either choice is valid!
Bottom line: When equal, just move one pointer (doesn’t matter which) and continue. The algorithm’s correctness doesn’t depend on this choice. 🎯