Problem Statement #

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Visual Representation:

       █
   █   █ █   █
 █ █ █ █ █ █ █ █
[0,1,0,2,1,0,1,3,2,1,2,1]

Water trapped (shown with ~):

       █
   █~~~█~█~~~█
 █~█~█~█~█~█~█~█
[0,1,0,2,1,0,1,3,2,1,2,1]

Conceptual Understanding #

To solve this problem effectively, we need to understand what determines how much water can be trapped at any given position. There are two primary approaches to thinking about this problem:

Approach 1: Shape-Based Analysis #

In this approach, we would identify distinct “containers” or shapes formed by the elevation map and calculate the area within each container. This method is more intuitive when dealing with 2D matrices or complex geographical problems where you need to find enclosed regions.

Approach 2: Column-Based Analysis (Optimal for This Problem) #

Instead of looking at shapes, we examine each position (column) individually and determine how much water can sit on top of that particular bar. This is the superior approach for this one-dimensional problem because:

1. Simplicity: We only need to consider one position at a time
2. Efficiency: We can leverage dynamic programming to avoid redundant calculations
3. Clarity: The logic is straightforward and easy to implement

The Key Insight #

For any given position i, the amount of water that can be trapped above it is determined by:

Water Height at position i = min(max_height_to_left, max_height_to_right) - height[i]

Why does this formula work?

• Maximum height to the left: This represents the tallest “wall” on the left side that could contain water
• Maximum height to the right: This represents the tallest “wall” on the right side that could contain water
• Minimum of both: Water will spill over the shorter of the two walls, so we take the minimum
• Subtract current height: The bar itself occupies space and displaces water

If the result is negative (when the current bar is taller than the containing walls), no water can be trapped, so we treat it as 0.

Solution: Dynamic Programming Approach #

The naive approach would be to scan left and right from each position to find the maximum heights. However, this would result in O(n²) time complexity. We can optimize this to O(n) using dynamic programming.

Strategy #

1. Pre-compute maximum heights: Create two arrays

   • leftMax[i]: Maximum height from index 0 to i (inclusive)
   • rightMax[i]: Maximum height from index i to end (inclusive)

2. Build left-to-right cache: Iterate from left to right

   • At each position, the maximum height to the left is either the current bar’s height or the maximum height we’ve seen so far

3. Build right-to-left cache: Iterate from right to left

   • At each position, the maximum height to the right is either the current bar’s height or the maximum height we’ve seen so far

4. Calculate trapped water: For each position

   • Apply our formula: min(leftMax[i], rightMax[i]) - height[i]
   • Sum up all the water trapped

Implementation #

var trap = function(height) {
    // Edge case: empty or very small arrays can't trap water
    if (height.length < 3) return 0;
    
    const cacheLeft = [];
    const cacheRight = [];
    
    // Populate both caches in a single pass
    for (let i = 0; i < height.length; i++) {
        // Left cache: max height from start to current position
        // Compare current height with the max seen so far (to the left)
        cacheLeft[i] = Math.max(cacheLeft[i - 1] || 0, height[i]);
        
        // Right cache: max height from current position to end
        // We build this from right to left using reverse indexing
        const rightIdx = height.length - i - 1;
        cacheRight[rightIdx] = Math.max(
            cacheRight[rightIdx + 1] || 0, 
            height[rightIdx]
        );
    }
    
    // Calculate total water trapped
    let result = 0;
    for (let i = 0; i < height.length; i++) {
        // Water height = min of max walls on both sides
        // Subtract the pillar height to get just the water
        const waterHeight = Math.min(cacheRight[i], cacheLeft[i]) - height[i];
        result += waterHeight;
    }
    
    return result;
};

Complexity Analysis #

Time Complexity: O(n)

• First loop: O(n) to build both caches
• Second loop: O(n) to calculate total water
• Total: O(n) + O(n) = O(n)

Space Complexity: O(n)

• We use two arrays of size n to store the left and right maximum heights
• This can be optimized to O(1) using a two-pointer approach (see alternative solutions)

Step-by-Step Example #

Let’s trace through the example [0,1,0,2,1,0,1,3,2,1,2,1]:

Step 1: Build cacheLeft

Index:     0  1  2  3  4  5  6  7  8  9  10 11
height:    0  1  0  2  1  0  1  3  2  1  2  1
cacheLeft: 0  1  1  2  2  2  2  3  3  3  3  3

Step 2: Build cacheRight

Index:      0  1  2  3  4  5  6  7  8  9  10 11
height:     0  1  0  2  1  0  1  3  2  1  2  1
cacheRight: 3  3  3  3  3  3  3  3  2  2  2  1

Step 3: Calculate water at each position

Index 0: min(0, 3) - 0 = 0
Index 1: min(1, 3) - 1 = 0
Index 2: min(1, 3) - 0 = 1  ← Water trapped!
Index 3: min(2, 3) - 2 = 0
Index 4: min(2, 3) - 1 = 1  ← Water trapped!
Index 5: min(2, 3) - 0 = 2  ← Water trapped!
Index 6: min(2, 3) - 1 = 1  ← Water trapped!
Index 7: min(3, 3) - 3 = 0
Index 8: min(3, 2) - 2 = 0
Index 9: min(3, 2) - 1 = 1  ← Water trapped!
Index 10: min(3, 2) - 2 = 0
Index 11: min(3, 1) - 1 = 0

Total: 0 + 0 + 1 + 0 + 1 + 2 + 1 + 0 + 0 + 1 + 0 + 0 = 6

Alternative Solutions #

Two-Pointer Approach (O(1) Space) #

While the dynamic programming approach is intuitive and easy to understand, we can further optimize space complexity using two pointers:

var trap = function(height) {
    if (height.length < 3) return 0;
    
    let left = 0;
    let right = height.length - 1;
    let leftMax = 0;
    let rightMax = 0;
    let result = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                result += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                result += rightMax - height[right];
            }
            right--;
        }
    }
    
    return result;
};

This approach uses O(1) space but maintains O(n) time complexity.

Common Pitfalls #

1. Off-by-one errors: Be careful with array indexing, especially when building the right cache
2. Negative water: Make sure your logic handles cases where bars are taller than containing walls
3. Edge cases: Arrays with fewer than 3 elements cannot trap water
4. Integer overflow: For very large inputs, ensure your accumulator doesn’t overflow

Related Problems #

• Container With Most Water: Similar but calculates the maximum area between two lines
• Largest Rectangle in Histogram: Uses similar stack-based techniques
• Trapping Rain Water II: 2D version requiring different approach (priority queue/heap)

Conclusion #

The Trapping Rain Water problem elegantly demonstrates how dynamic programming can transform a seemingly complex problem into an efficient solution. By pre-computing the maximum heights on both sides, we avoid redundant work and achieve linear time complexity. The key insight—that water level at each position depends only on the minimum of the maximum heights on both sides—makes this problem both interesting and practical for understanding real-world scenarios like water drainage systems and terrain analysis.