Trapping Rain Water

Hardarraytwo-pointersstackdynamic-programming
Category: Two Pointers
Companies that ask this question:
AmazonGoogleFacebookMicrosoftApple
LeetCode →NeetCode →

Approach

Trapping Rain Water

Problem

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

Visualization:
   █
 █ ██ █
█████████

Water trapped (shown as ~):
   █
 █~██~█
█████████

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Approach 1: Two Pointers (Optimal)

Intuition

Water level at any position is determined by the minimum of max heights to its left and right. Instead of precomputing these, we can use two pointers to track them dynamically.

Key Insight

  • Use left and right pointers
  • Track leftMax and rightMax as we go
  • Move the pointer with smaller max height
  • Water at current position = min(leftMax, rightMax) - height[current]

Algorithm

def trap(height):
    if not height:
        return 0
    
    left, right = 0, len(height) - 1
    leftMax, rightMax = height[left], height[right]
    water = 0
    
    while left < right:
        if leftMax < rightMax:
            left += 1
            leftMax = max(leftMax, height[left])
            water += leftMax - height[left]
        else:
            right -= 1
            rightMax = max(rightMax, height[right])
            water += rightMax - height[right]
    
    return water

Example Walkthrough

For [0,1,0,2,1,0,1,3,2,1,2,1]:

Initial: left=0, right=11, leftMax=0, rightMax=1
Move left: left=1, leftMax=1, water += 1-1 = 0
Move left: left=2, leftMax=1, water += 1-0 = 1
Move left: left=3, leftMax=2, water += 2-2 = 1
...

Time Complexity

  • O(n): Single pass with two pointers

Space Complexity

  • O(1): Only using variables

Approach 2: Dynamic Programming

Intuition

For each position, precompute:

  • leftMax[i]: Max height to the left
  • rightMax[i]: Max height to the right

Water at position i: min(leftMax[i], rightMax[i]) - height[i]

Algorithm

def trap(height):
    if not height:
        return 0
    
    n = len(height)
    leftMax = [0] * n
    rightMax = [0] * n
    
    # Fill leftMax
    leftMax[0] = height[0]
    for i in range(1, n):
        leftMax[i] = max(leftMax[i-1], height[i])
    
    # Fill rightMax
    rightMax[n-1] = height[n-1]
    for i in range(n-2, -1, -1):
        rightMax[i] = max(rightMax[i+1], height[i])
    
    # Calculate water
    water = 0
    for i in range(n):
        water += min(leftMax[i], rightMax[i]) - height[i]
    
    return water

Time Complexity

  • O(n): Three passes

Space Complexity

  • O(n): Two arrays

Approach 3: Stack

Use a monotonic decreasing stack to find boundaries for water pockets.

Time Complexity

  • O(n): Each element pushed/popped once

Space Complexity

  • O(n): Stack storage

Which Approach to Use?

  • Two Pointers (Approach 1): Best - O(1) space, single pass
  • DP (Approach 2): Easier to understand, but uses O(n) space
  • Stack (Approach 3): Alternative approach, good for understanding

Two pointers is the optimal solution for interviews.

Solution

java
1/**
2 * Trapping Rain Water
3 * Time: O(n) for all approaches
4 * Space: O(1) for two pointers, O(n) for DP and stack
5 */
6
7import java.util.*;
8
9// Approach 1: Two Pointers (Optimal - O(1) space)
10class Solution {
11    public int trap(int[] height) {
12        if (height == null || height.length == 0) {
13            return 0;
14        }
15        
16        int left = 0, right = height.length - 1;
17        int leftMax = height[left], rightMax = height[right];
18        int water = 0;
19        
20        while (left < right) {
21            if (leftMax < rightMax) {
22                left++;
23                leftMax = Math.max(leftMax, height[left]);
24                water += leftMax - height[left];
25            } else {
26                right--;
27                rightMax = Math.max(rightMax, height[right]);
28                water += rightMax - height[right];
29            }
30        }
31        
32        return water;
33    }
34}
35
36// Approach 2: Dynamic Programming - O(n) space
37class Solution2 {
38    public int trap(int[] height) {
39        if (height == null || height.length == 0) {
40            return 0;
41        }
42        
43        int n = height.length;
44        int[] leftMax = new int[n];
45        int[] rightMax = new int[n];
46        
47        // Fill leftMax
48        leftMax[0] = height[0];
49        for (int i = 1; i < n; i++) {
50            leftMax[i] = Math.max(leftMax[i-1], height[i]);
51        }
52        
53        // Fill rightMax
54        rightMax[n-1] = height[n-1];
55        for (int i = n-2; i >= 0; i--) {
56            rightMax[i] = Math.max(rightMax[i+1], height[i]);
57        }
58        
59        // Calculate water
60        int water = 0;
61        for (int i = 0; i < n; i++) {
62            water += Math.min(leftMax[i], rightMax[i]) - height[i];
63        }
64        
65        return water;
66    }
67}
68
69// Approach 3: Stack
70class Solution3 {
71    public int trap(int[] height) {
72        Deque<Integer> stack = new ArrayDeque<>();
73        int water = 0;
74        
75        for (int i = 0; i < height.length; i++) {
76            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
77                int top = stack.pop();
78                if (stack.isEmpty()) {
79                    break;
80                }
81                
82                int distance = i - stack.peek() - 1;
83                int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top];
84                water += distance * boundedHeight;
85            }
86            
87            stack.push(i);
88        }
89        
90        return water;
91    }
92}
93
Loading visualizer...