Trapping Rain Water | Leetcode 42

Welcome to our deep dive on Trapping Rain Water (Leetcode 42). This famous hard problem bridges identical underlying concepts across Brute Force, Dynamic Programming, and optimal Two Pointers!

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: height = [0,1,0,2,1,0,1,3,2,1,2,1] => Output: 6

Core Concept: How water traps

At any specific index i, how much water sits on top of that specific building block? Water is constrained by the tallest building on its left and the tallest building on its right. Specifically, the water level will be the minimum of those two peak heights. Water[i] = min(MaxLeft, MaxRight) - height[i]

(If this value is negative, it means the building is taller than the trapped water bounds, so we trap 0 water).

Approach 1: Dynamic Programming Precomputation O(N) Time / O(N) Space

Instead of scanning left and right for every single index (O(N^2) brute force), we can simply create two arrays: max_left and max_right.

1. We iterate forwards once to build max_left, caching the highest wall seen so far.
2. We iterate backwards once to build max_right, caching the highest wall seen so far.
3. Then we do a final linear pass calculating the trapped water at i using our O(1) cached values!

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: return 0
        
        n = len(height)
        max_left = [0] * n
        max_right = [0] * n
        
        max_left[0] = height[0]
        for i in range(1, n):
            max_left[i] = max(max_left[i-1], height[i])
            
        max_right[n-1] = height[n-1]
        for i in range(n-2, -1, -1):
            max_right[i] = max(max_right[i+1], height[i])
            
        total_water = 0
        for i in range(n):
            total_water += min(max_left[i], max_right[i]) - height[i]
            
        return total_water

Approach 2: Optimal Two-Pointers O(N) Time / O(1) Space

We don't actually need full precomputed arrays. We notice that the water level is dictated by min(MaxLeft, MaxRight). If MaxLeft < MaxRight, then the MaxLeft wall is strictly the bottleneck! Even if there's a gigantic wall further to the right, it doesn't matter. The water will spill over the MaxLeft bottleneck.

Thus, we can use a left and right pointer squeezing inwards. If left_max < right_max, we can safely calculate the water vertically above the left pointer and advance it! We don't care about what sits between left and right.

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: return 0
        
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        total_water = 0
        
        while left < right:
            if left_max < right_max:
                left += 1
                left_max = max(left_max, height[left])
                total_water += left_max - height[left]
            else:
                right -= 1
                right_max = max(right_max, height[right])
                total_water += right_max - height[right]
                
        return total_water

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (42)