32. Trapping Rain Water
🔗 LeetCode Problem: 42. Trapping Rain Water
📊 Difficulty: Hard
🏷️ Topics: Array, Two Pointers, Dynamic Programming, Stack
Problem Statement
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1].
In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
Constraints:
- n == height.length
- 1 <= n <= 2 * 10^4
- 0 <= height[i] <= 10^5
🎨 Visual Understanding
The Problem Visualized
height = [0,1,0,2,1,0,1,3,2,1,2,1]
Elevation map:
██
██ ██ ██
██ ██ ██ ██ ██ ██
██ ██ ██ ██ ██ ██ ██ ██
────────────────────────────────────
0 1 0 2 1 0 1 3 2 1 2 1
With trapped water (░░):
██
██░░░░░░░░░░██░░██
██░░██░░██░░░░░░██░░██░░██
██░░██░░██░░██░░██░░██░░██░░██
────────────────────────────────────
0 1 0 2 1 0 1 3 2 1 2 1
Water trapped at each position:
0 0 1 0 1 2 1 0 0 1 0 0 → Total = 6
Key Observation: Water Level at Each Position
Water at position i depends on:
1. Highest bar to its LEFT (leftMax)
2. Highest bar to its RIGHT (rightMax)
Water level = min(leftMax, rightMax) - height[i]
Example at index 5 (height = 0):
leftMax = 2 (highest bar to left)
rightMax = 3 (highest bar to right)
water = min(2, 3) - 0 = 2 - 0 = 2 units
Why min()?
Water level limited by the SHORTER wall
(water would overflow the shorter side)
Why min(leftMax, rightMax)?
Position with height = 0, leftMax = 5, rightMax = 3:
██ ██
██ ██
██ ░░░░ ██
██ ░░░░ ██
██ ░░░░ ██
─────────────────────────────
5 ... 0 ... 3
Water level = min(5, 3) = 3
Water trapped = 3 - 0 = 3 units
Can't go higher than 3 because right wall is only 3
(water would overflow on the right side)
🎯 Approach 1: Brute Force
The Most Natural Thinking 💭
Core Logic:
For each position, find water trapped:
1. Find leftMax: highest bar to the left
2. Find rightMax: highest bar to the right
3. Water = min(leftMax, rightMax) - height[i]
4. Sum up water at all positions
Why This Works: - Checks each position independently - Guaranteed to find all water - Easy to understand
Why This Fails Requirements: - Time complexity O(n²) - For each position, scan entire array twice - Too slow for large inputs - Not optimal for interviews
Implementation
public int trap(int[] height) {
int n = height.length;
int totalWater = 0;
for (int i = 0; i < n; i++) {
// Find leftMax
int leftMax = 0;
for (int j = 0; j <= i; j++) {
leftMax = Math.max(leftMax, height[j]);
}
// Find rightMax
int rightMax = 0;
for (int j = i; j < n; j++) {
rightMax = Math.max(rightMax, height[j]);
}
// Calculate water at position i
int water = Math.min(leftMax, rightMax) - height[i];
totalWater += water;
}
return totalWater;
}
⏰ Time: O(n²) - for each position, scan array twice
💾 Space: O(1) - only variables
🎯 Approach 2: Dynamic Programming
The Improved Thinking 💭
Core Logic:
Precompute leftMax and rightMax arrays:
1. leftMax[i] = max height from 0 to i
2. rightMax[i] = max height from i to n-1
3. For each position: water = min(leftMax[i], rightMax[i]) - height[i]
Why This Works: - Avoids redundant calculations - Precompute once, use many times - O(n) time complexity
Why This Could Be Better: - Uses O(n) extra space for arrays - Can we do better with space?
Implementation
public int trap(int[] height) {
int n = height.length;
if (n == 0) return 0;
// Precompute leftMax for each position
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
// Precompute rightMax for each position
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
// Calculate total water
int totalWater = 0;
for (int i = 0; i < n; i++) {
int water = Math.min(leftMax[i], rightMax[i]) - height[i];
totalWater += water;
}
return totalWater;
}
⏰ Time: O(n) - three passes through array
💾 Space: O(n) - two arrays
✅ Approach 3: Two Pointers (Optimal)
The Breakthrough Insight 💡
Core Logic:
Use two pointers to track leftMax and rightMax dynamically:
Key insight: Water level depends on the SHORTER wall
- If leftMax < rightMax: water at left limited by leftMax
- If rightMax < leftMax: water at right limited by rightMax
Algorithm:
1. Start with left=0, right=n-1
2. Track leftMax and rightMax as we go
3. Process the side with SHORTER max height
4. Move pointer inward after processing
Visual Explanation:
height = [0,1,0,2,1,0,1,3,2,1,2,1]
L R
leftMax = 0, rightMax = 1
If leftMax < rightMax:
→ Water at left limited by leftMax (shorter wall)
→ Process left side, move left pointer right
If rightMax < leftMax:
→ Water at right limited by rightMax (shorter wall)
→ Process right side, move right pointer left
Key: We don't need to know the EXACT max on other side,
just need to know which side has SHORTER max
Why This Works:
Suppose leftMax < rightMax:
For position at left:
- We know leftMax
- We know rightMax > leftMax (guaranteed)
- Water level = min(leftMax, rightMax) = leftMax
- We can calculate water even without exact rightMax value!
This is the key insight that enables O(1) space solution
Implementation
public int trap(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int left = 0;
int right = height.length - 1;
int leftMax = 0;
int rightMax = 0;
int totalWater = 0;
while (left < right) {
if (height[left] < height[right]) {
// Process left side (left wall is shorter)
if (height[left] >= leftMax) {
// Current position is a new peak, update leftMax
leftMax = height[left];
} else {
// Can trap water here
totalWater += leftMax - height[left];
}
left++;
} else {
// Process right side (right wall is shorter or equal)
if (height[right] >= rightMax) {
// Current position is a new peak, update rightMax
rightMax = height[right];
} else {
// Can trap water here
totalWater += rightMax - height[right];
}
right--;
}
}
return totalWater;
}
⏰ Time: O(n) - single pass with two pointers
💾 Space: O(1) - only a few variables
🔍 Step-by-Step Execution
Example: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Initial State:
═══════════════════════════════════════════════════════════════════
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
L R
leftMax = 0, rightMax = 0, totalWater = 0
Step 1: Compare height[left] vs height[right]
═══════════════════════════════════════════════════════════════════
height[0]=0 < height[11]=1 → Process left side
height[0]=0 >= leftMax=0? → Yes, update leftMax
leftMax = 0 (no change)
No water trapped (height equals leftMax)
left = 1
State: leftMax=0, rightMax=0, water=0
Step 2: left=1, right=11
═══════════════════════════════════════════════════════════════════
height[1]=1 < height[11]=1? → No (equal), process right side
height[11]=1 >= rightMax=0? → Yes, update rightMax
rightMax = 1
No water trapped
right = 10
State: leftMax=0, rightMax=1, water=0
Step 3: left=1, right=10
═══════════════════════════════════════════════════════════════════
height[1]=1 < height[10]=2 → Process left side
height[1]=1 >= leftMax=0? → Yes, update leftMax
leftMax = 1
No water trapped
left = 2
State: leftMax=1, rightMax=1, water=0
Step 4: left=2, right=10
═══════════════════════════════════════════════════════════════════
height[2]=0 < height[10]=2 → Process left side
height[2]=0 >= leftMax=1? → No
Water trapped = leftMax - height[2] = 1 - 0 = 1
totalWater = 0 + 1 = 1
left = 3
State: leftMax=1, rightMax=1, water=1
Step 5: left=3, right=10
═══════════════════════════════════════════════════════════════════
height[3]=2 < height[10]=2? → No (equal), process right side
height[10]=2 >= rightMax=1? → Yes, update rightMax
rightMax = 2
No water trapped
right = 9
State: leftMax=1, rightMax=2, water=1
Step 6: left=3, right=9
═══════════════════════════════════════════════════════════════════
height[3]=2 < height[9]=1? → No, process right side
height[9]=1 >= rightMax=2? → No
Water trapped = rightMax - height[9] = 2 - 1 = 1
totalWater = 1 + 1 = 2
right = 8
State: leftMax=1, rightMax=2, water=2
Step 7: left=3, right=8
═══════════════════════════════════════════════════════════════════
height[3]=2 == height[8]=2 → Process right side
height[8]=2 >= rightMax=2? → Yes (equal)
rightMax = 2 (no change)
No water trapped
right = 7
State: leftMax=1, rightMax=2, water=2
Step 8: left=3, right=7
═══════════════════════════════════════════════════════════════════
height[3]=2 < height[7]=3 → Process left side
height[3]=2 >= leftMax=1? → Yes, update leftMax
leftMax = 2
No water trapped
left = 4
State: leftMax=2, rightMax=2, water=2
Step 9: left=4, right=7
═══════════════════════════════════════════════════════════════════
height[4]=1 < height[7]=3 → Process left side
height[4]=1 >= leftMax=2? → No
Water trapped = leftMax - height[4] = 2 - 1 = 1
totalWater = 2 + 1 = 3
left = 5
State: leftMax=2, rightMax=2, water=3
Step 10: left=5, right=7
═══════════════════════════════════════════════════════════════════
height[5]=0 < height[7]=3 → Process left side
height[5]=0 >= leftMax=2? → No
Water trapped = leftMax - height[5] = 2 - 0 = 2
totalWater = 3 + 2 = 5
left = 6
State: leftMax=2, rightMax=2, water=5
Step 11: left=6, right=7
═══════════════════════════════════════════════════════════════════
height[6]=1 < height[7]=3 → Process left side
height[6]=1 >= leftMax=2? → No
Water trapped = leftMax - height[6] = 2 - 1 = 1
totalWater = 5 + 1 = 6
left = 7
State: leftMax=2, rightMax=2, water=6
Step 12: left=7, right=7
═══════════════════════════════════════════════════════════════════
left >= right → Loop terminates
═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 6
═══════════════════════════════════════════════════════════════════
Another Example: height = [4,2,0,3,2,5]
Visual:
██
██ ██
██░░██░░░░░░██░░██
██░░██░░░░██░░██░░██
██░░██░░██░░██░░██░░██
██░░██░░██░░██░░██░░██
─────────────────────────────
4 2 0 3 2 5
Step-by-step:
left=0, right=5: 4 < 5 → leftMax=4, left=1
left=1, right=5: 2 < 5 → water=4-2=2, left=2
left=2, right=5: 0 < 5 → water=4-0=4, total=6, left=3
left=3, right=5: 3 < 5 → water=4-3=1, total=7, left=4
left=4, right=5: 2 < 5 → water=4-2=2, total=9, left=5
left=5, right=5 → Stop
Result: 9
🔍 Edge Cases
Case 1: Flat surface (no water can be trapped)
Input: height = [1, 1, 1, 1]
Output: 0
Explanation: No valleys to trap water
Case 2: Single element
Input: height = [5]
Output: 0
Explanation: Need at least two bars to trap water
Case 3: Two elements
Input: height = [3, 2]
Output: 0
Explanation: Water flows off the side
Case 4: Valley in middle
Input: height = [3, 0, 2]
Output: 2
Explanation: 2 units trapped in the middle
Case 5: All ascending
Input: height = [1, 2, 3, 4, 5]
Output: 0
Explanation: No valleys
Case 6: All descending
Input: height = [5, 4, 3, 2, 1]
Output: 0
Explanation: No valleys
Case 7: Multiple peaks
Input: height = [4, 2, 3]
Output: 1
Explanation: 1 unit at index 1
Case 8: Large values
Input: height = [100000, 0, 100000]
Output: 100000
Explanation: Large valley in middle
Common Mistakes
Mistake 1: Forgetting that water level depends on min(leftMax, rightMax)
❌ Wrong:
int water = leftMax - height[i]; // Ignoring rightMax
✓ Right:
int water = Math.min(leftMax, rightMax) - height[i];
Reason: Water level limited by shorter wall
Mistake 2: Not checking if current height is a new peak
❌ Wrong:
if (height[left] < height[right]) {
totalWater += leftMax - height[left];
left++;
}
✓ Right:
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
totalWater += leftMax - height[left];
}
left++;
Reason: Need to update max before calculating water
Mistake 3: Wrong loop condition
❌ Wrong:
while (left <= right) { // Equal case problematic
...
}
✓ Right:
while (left < right) {
...
}
Reason: Can't trap water at the same position
Mistake 4: Processing wrong side
❌ Wrong:
if (height[left] < height[right]) {
// Process right side (wrong!)
...
right--;
}
✓ Right:
if (height[left] < height[right]) {
// Process left side (left wall is shorter)
...
left++;
}
Reason: Process the side with shorter wall
Mistake 5: Adding negative water
❌ Wrong:
int water = leftMax - height[i];
totalWater += water; // Could be negative if height[i] > leftMax
✓ Right:
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
totalWater += leftMax - height[left];
}
Reason: Only add water when there's a valley
Mistake 6: Not handling empty array
❌ Wrong:
int left = 0;
int right = height.length - 1; // Crash if empty
✓ Right:
if (height == null || height.length == 0) return 0;
Reason: Need to check for empty input
🎯 Key Takeaways
⚡ Algorithm Comparison
Approach 1: Brute Force
Time: O(n²)
Space: O(1)
Use: Only for understanding
Approach 2: Dynamic Programming
Time: O(n)
Space: O(n)
Use: Good solution, easier to understand
Approach 3: Two Pointers (RECOMMENDED)
Time: O(n)
Space: O(1)
Use: Optimal solution, best for interviews
🔑 The Core Insight
Water Trapping Formula:
water[i] = min(leftMax[i], rightMax[i]) - height[i]
Why min()?
Water level limited by the SHORTER wall
(water overflows from shorter side)
Two Pointers Key Insight:
- We don't need exact max on both sides
- Only need to know which side has SHORTER max
- Process the side with shorter max
- This enables O(1) space solution
Algorithm:
1. Compare height[left] vs height[right]
2. Process the SHORTER side (more limiting)
3. Update max if current is peak, else add water
4. Move pointer inward
5. Repeat until pointers meet
Decision Rule:
if height[left] < height[right]:
→ Left wall is shorter/more limiting
→ Process left side, use leftMax
→ Move left++
else:
→ Right wall is shorter/more limiting
→ Process right side, use rightMax
→ Move right--
🎯 Pattern Recognition
Problem Type: Array Processing with Constraints
Core Pattern: Two Pointers + Greedy
When to Apply:
✓ Need to track max from both directions
✓ Decision depends on comparison from both ends
✓ Can process one side at a time
✓ Want O(1) space solution
Key Techniques:
→ Two pointers from opposite ends
→ Track running max from both sides
→ Process side with more limiting constraint
→ Greedy approach: process shorter side first
Related Problems:
- Container With Most Water (LC 11)
- Product of Array Except Self (LC 238)
- Next Greater Element (LC 496)
🧠 Interview Strategy
Step 1: "Need to trap water between elevation bars"
Step 2: "Water at each position = min(leftMax, rightMax) - height"
Step 3: "Brute force: O(n²) - find max for each position"
Step 4: "DP: O(n) time, O(n) space - precompute arrays"
Step 5: "Two pointers: O(n) time, O(1) space - process shorter side"
Key Points to Mention:
- Water level limited by shorter wall
- Two pointers process one side at a time
- Update max when hitting peak
- Add water when in valley
- O(n) time, O(1) space optimal
📝 Quick Revision Notes
🎯 Core Concept:
Water at position i = min(leftMax, rightMax) - height[i]. Use two pointers to process shorter side first, achieving O(1) space.
⚡ Quick Implementation:
public int trap(int[] a) {
int len = a.length;
int trappedWater = 0;
// // Approach 1 - brute force. We should understand this.
// // check diagram on LC for intuition. Very clear if we see diagram
// // No water will be stored at i = 0 and i = len - 1. Hence, do not consider these
// // indices that water gets trapped. Water gets lodged only between i = 1 and i = len -2
// for(int i = 1; i < len - 1; i++) {
// // For example, for i = 3, we need to find maximum heights on the
// // left and right sides. Get the minimum of them as water cannot gets
// // stored above min of those 2 heights. And do minus the current height.
// int leftMax = Integer.MIN_VALUE;
// for(int j = 0; j <= i; j++) { // includes j = 0
// leftMax = Math.max(leftMax, a[j]);
// }
// int rightMax = Integer.MIN_VALUE;
// for(int j = i; j < len; j++) { // includes j = len - 1
// rightMax = Math.max(rightMax, a[j]);
// }
// int trappedHere = Math.min(leftMax, rightMax) - a[i];
// if(trappedHere > 0) {
// trappedWater += trappedHere;
// }
// }
// // Approach 2 - Maintain 2 separate arrays to keep track the
// // leftMax and rightMax to calculate the trapped water for each of the index.
// int[] leftMax = new int[len]; // leftMax[0] = 0
// int[] rightMax = new int[len]; // rightMax[len - 1] = 0
// // calculate leftMax
// int currMax = 0;
// for(int i = 1; i < len; i++) {
// currMax = Math.max(currMax, a[i-1]);
// leftMax[i] = currMax;
// }
// // calculate rightMax
// currMax = 0;
// for(int i = len - 2; i >= 0; i--) {
// currMax = Math.max(currMax, a[i+1]);
// rightMax[i] = currMax;
// }
// // Now, calculate the trapped water at each index
// // We know that we need to ignore i = 0 and i = len - 1
// for(int i = 1; i < len - 1; i++) {
// int trappedHere = Math.min(leftMax[i], rightMax[i]) - a[i];
// if(trappedHere > 0) {
// trappedWater += trappedHere;
// }
// }
// Approach 3 - using 2 pointers. Simple concept, but little tricky
int left = 1; // always trapping calculation starts from i = 1 to i = len - 2
int right = len - 2; // always trapping calculation starts from i = 1 to i = len - 2
int leftMax = a[0]; // initial left max for a[1]
int rightMax = a[len - 1]; // initial right max for a[len - 2]
while (left <= right) {
if(leftMax < rightMax) {
int trappedHere = Math.min(leftMax, rightMax) - a[left];
if(trappedHere > 0) {
trappedWater += trappedHere;
}
// why? If the left wall (leftMax) is lower than the right wall (rightMax), then
// near the left, the water level is capped by the left wall, irrespective of what’s
// further on the right. So process left.
left++; // move left until leftMax < rightMax
leftMax = Math.max(leftMax, a[left - 1]); // new max
} else {
int trappedHere = Math.min(leftMax, rightMax) - a[right];
if(trappedHere > 0) {
trappedWater += trappedHere;
}
right--; // move right until leftMax > rightMax
rightMax = Math.max(rightMax, a[right + 1]); // new max
}
}
return trappedWater;
}
🔑 Key Insights:
- Formula:
water[i] = min(leftMax, rightMax) - height[i] - Why min(): Water level limited by SHORTER wall
- Two pointers: Process side with shorter max height
- Decision:
height[left] < height[right]→ process left - Update max: When current position is peak
- Add water: When current position is valley
- Loop condition:
left < right(can't trap at same position) - Time: O(n), Space: O(1)
- Key insight: Don't need exact max on other side, just need to know which is shorter
🎪 Memory Aid:
"Water trapped by SHORTER wall! Process SHORTER side!"
Think: "Two pointers squeeze, update max or add water"
Related Patterns
- Container With Most Water (LC 11)
- Product of Array Except Self (LC 238)
- Largest Rectangle in Histogram (LC 84)
- Next Greater Element (LC 496)
Happy practicing! 🎯