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.

Practice

1. What does the Trapping Rain Water problem ask you to find given an array of heights?

easy

A. The number of bars taller than a given height

B. The highest bar in the array

C. The total amount of water that can be trapped between the bars after raining

D. The sum of all bar heights

Solution

1. Step 1: Understand the problem context

   The problem gives an array representing heights of bars and asks how much water can be trapped between them after rain.

2. Step 2: Identify the goal

   The goal is to calculate the total trapped water volume between bars, not just the tallest bar or sum of heights.

3. Final Answer:

   The total amount of water trapped between bars -> Option C

4. Quick Check:

   Trapped water = total water held between bars [OK]

Hint: Focus on trapped water volume, not bar heights [OK]

Common Mistakes:

• Confusing trapped water with tallest bar height
• Summing bar heights instead of water trapped
• Ignoring spaces between bars where water collects

2. Which of the following Python code snippets correctly initializes two pointers for the two-pointer approach in the Trapping Rain Water problem?

easy

A. left, right = 0, len(height) - 1

B. left, right = 1, len(height)

C. left, right = 0, len(height)

D. left, right = -1, len(height) - 1

Solution

1. Step 1: Understand pointer initialization

   Two pointers start at the ends: left at 0, right at last index (length - 1).

2. Step 2: Check each option

   left, right = 0, len(height) - 1 correctly sets left=0 and right=len(height)-1. Others have invalid indices.

3. Final Answer:

   left, right = 0, len(height) - 1 -> Option A

4. Quick Check:

   Start pointers at array ends [OK]

Hint: Two pointers start at first and last index [OK]

Common Mistakes:

• Setting right pointer to len(height) (out of range)
• Starting left pointer at 1 instead of 0
• Using negative indices incorrectly

3. What is the output of the following Python code for trapping rain water?

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))

medium

A. 5

B. 6

C. 4

D. 7

Solution

1. Step 1: Trace pointers and water accumulation

   Using two pointers, water trapped is calculated by comparing left and right heights and updating max heights.

2. Step 2: Calculate trapped water for given input

   For input [0,1,0,2,1,0,1,3,2,1,2,1], total trapped water is 6 units.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Standard example result = 6 [OK]

Hint: Use two-pointer method to sum trapped water [OK]

Common Mistakes:

• Miscounting trapped water units
• Not updating max heights correctly
• Confusing left and right pointer moves

4. Find the error in this Python code snippet for the Trapping Rain Water problem:

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while left <= right:
        if height[left] < height[right]:
            if height[left] > left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] > right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

medium

A. The while loop condition should be 'left < right' instead of 'left <= right'

B. The comparison operators '>' should be '>=' when updating max heights

C. The water accumulation formula is incorrect

D. The pointers should be initialized to 1 and len(height) - 2

Solution

1. Step 1: Analyze the loop condition

   The loop uses 'left <= right', which causes pointers to cross and double count or error.

2. Step 2: Correct loop condition

   Changing to 'left < right' prevents overlap and ensures correct water calculation.

3. Final Answer:

   The while loop condition should be 'left < right' instead of 'left <= right' -> Option A

4. Quick Check:

   Loop ends before pointers cross [OK]

Hint: Use strict less than in loop to avoid pointer overlap [OK]

Common Mistakes:

• Using <= causes double counting
• Not updating max heights correctly
• Incorrect pointer initialization

5. Given the height array [4,2,0,3,2,5], what is the total trapped rain water? Use the two-pointer approach to solve.

hard

A. 7

B. 8

C. 6

D. 9

Solution

1. Step 1: Initialize pointers and max heights

   left=0, right=5, left_max=0, right_max=0, water=0.

2. Step 2: Move pointers and calculate trapped water

   Walk through: - left=0 (4), right=5 (5), left < right - height[left]

3. Final Answer:

   9 -> Option D

4. Quick Check:

   Sum trapped water units = 9 [OK]

Hint: Add water trapped at each step using max heights [OK]

Common Mistakes:

• Miscounting trapped water at zero height bars
• Not updating left_max and right_max correctly
• Stopping loop too early or late