📚 Table of Contents
📋 Problem Statement
Each index in height is a vertical bar of width 1. Return the total trapped
water after raining.
Examples
Example 1:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]Output: 6
Example 2:
Input: [4,2,0,3,2,5]Output: 9
🎯 Real-World Analogy
Water Between Retaining Walls
Picture valleys between concrete walls. Water level at each valley point is capped by the shorter of the tallest wall on the left and right.
If the current wall is shorter than that cap, the difference becomes trapped water.
💡 Key Insights
- Water at index i:
min(leftMax, rightMax) - height[i]. - Two-pointer trick works by moving the smaller boundary inward.
- When left boundary is smaller, right boundary cannot reduce left-side cap.
- Single pass with running maxima yields O(1) extra space.
💻 Solution Approaches
Approach 1: Brute Force (Per Index Scan)
Time: O(N²) | Space: O(1)
Approach 2: Prefix/Suffix Max Arrays
Time: O(N) | Space: O(N)
Approach 3: Two Pointers (Recommended)
Time: O(N) | Space: O(1)
Python Implementation
from typing import List
def trap(height: List[int]) -> int:
left, right = 0, len(height) - 1
left_max = 0
right_max = 0
water = 0
while left < right:
if height[left] <= height[right]:
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water
JavaScript Implementation
function trap(height) {
let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let water = 0;
while (left < right) {
if (height[left] <= height[right]) {
leftMax = Math.max(leftMax, height[left]);
water += leftMax - height[left];
left += 1;
} else {
rightMax = Math.max(rightMax, height[right]);
water += rightMax - height[right];
right -= 1;
}
}
return water;
}
🔍 Step-by-Step Walkthrough
Trace [4,2,0,3,2,5]:
left=0,right=5,leftMax=0,rightMax=0,water=0
left side chosen -> leftMax=4, add 0
index1 height2 -> add 4-2=2
index2 height0 -> add 4-0=4 (water=6)
index3 height3 -> add 1 (water=7)
index4 height2 -> add 2 => 9
⚡ Complexity Analysis
Time: O(N) because each pointer moves inward at most N steps total.
Space: O(1) with constant state for boundaries and maxima.
🔧 Edge Cases
- Length less than 3 -> always 0 water.
- Monotonic increasing or decreasing bars -> 0 water.
- Plateaus (equal heights) across valleys.
- Very tall boundary walls at ends.
🧪 Test Cases
Python
def test_trap():
assert trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6
assert trap([4,2,0,3,2,5]) == 9
assert trap([1,2,3,4]) == 0
assert trap([4,3,2,1]) == 0
print("all tests passed")JavaScript
function testTrap() {
console.assert(trap([0,1,0,2,1,0,1,3,2,1,2,1]) === 6, "test 1");
console.assert(trap([4,2,0,3,2,5]) === 9, "test 2");
console.assert(trap([1,2,3,4]) === 0, "test 3");
console.assert(trap([4,3,2,1]) === 0, "test 4");
console.log("all tests passed");
}💼 Interview Tips
- State the water formula and explain each component.
- Justify why moving the smaller boundary is safe.
- Compare O(N) space vs O(1) space approaches.
- Use a mini pointer trace to prove correctness.
🎓 Key Takeaways
- Boundary minima determine trapped water height.
- Two pointers reduce space from O(N) to O(1).
- Pointer movement logic is the key interview differentiator.