Trapping Rain Water Problem in DSA Python

Mental Model

Imagine bars of different heights and rainwater filling the gaps between them. The water trapped depends on the tallest bars on the left and right sides.

Analogy: Think of a row of buildings with different heights after rain. Water collects in the valleys between taller buildings, just like water trapped between bars.

Height bars: 3 0 2 0 4
Water trapped:   _   _     
Representation:
3 ↑       
2 ↑   ↑   
1 ↑   ↑   ↑
0 ↑ ↑ ↑ ↑ ↑
Index: 0 1 2 3 4

Dry Run Walkthrough

Input: height = [3, 0, 2, 0, 4]

Goal: Calculate total units of water trapped between bars after rain

Step 1: Calculate max height to the left for each bar

left_max = [3, 3, 3, 3, 4]

Why: We need to know the tallest bar on the left to determine water level

Step 2: Calculate max height to the right for each bar

right_max = [4, 4, 4, 4, 4]

Why: We need to know the tallest bar on the right to determine water level

Step 3: Calculate trapped water at each bar by min(left_max, right_max) - height

water = [0, 3, 1, 3, 0]

Why: Water trapped depends on the smaller max height side minus current bar height

Step 4: Sum all trapped water units

total_water = 7

Why: Total trapped water is sum of water trapped at each bar

Result:

Water trapped at bars: 0 -> 3 -> 1 -> 3 -> 0
Total trapped water = 7

Annotated Code

DSA Python

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0

        left_max = [0] * n
        right_max = [0] * n

        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])  # track tallest bar from left

        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])  # track tallest bar from right

        trapped_water = 0
        for i in range(n):
            water_level = min(left_max[i], right_max[i])
            trapped_water += water_level - height[i]  # water trapped on current bar

        return trapped_water

# Driver code
sol = Solution()
height = [3, 0, 2, 0, 4]
print(sol.trap(height))

left_max[i] = max(left_max[i - 1], height[i]) # track tallest bar from left

build left max array to know tallest bar to the left of each position

right_max[i] = max(right_max[i + 1], height[i]) # track tallest bar from right

build right max array to know tallest bar to the right of each position

water_level = min(left_max[i], right_max[i])

water level at current bar limited by smaller tallest bar on either side

trapped_water += water_level - height[i] # water trapped on current bar

add trapped water at current bar to total

Output

7

Complexity Analysis

Time: O(n) because we traverse the height array a few times but only once each for left max, right max, and water calculation

Space: O(n) because we use two extra arrays to store left max and right max heights

vs Alternative: Compared to a naive approach that checks left and right max for each bar separately (O(n^2)), this method is much faster by precomputing max arrays

Edge Cases

empty height array

returns 0 as no bars means no water trapped

DSA Python

if n == 0:
            return 0

all bars of same height

returns 0 because no valleys to trap water

DSA Python

water_level = min(left_max[i], right_max[i])

strictly increasing or decreasing bars

returns 0 because water cannot be trapped on slopes

DSA Python

water_level - height[i]

When to Use This Pattern

When you see a problem asking how much water can be trapped between bars or heights, use the trapping rain water pattern by precomputing max heights from left and right to find water levels.

Common Mistakes

Mistake: Calculating trapped water using max height on only one side
Fix: Use the minimum of left max and right max heights to determine water level

Mistake: Not handling empty input array leading to errors
Fix: Add a guard clause to return 0 if input array is empty

Summary

Calculates total water trapped between bars after rain using precomputed max heights.

Use when you need to find how much water can be trapped between bars of different heights.

The trapped water at each bar depends on the smaller tallest bar on its left and right sides.