Trapping Rain Water Problem in DSA Python - Execution Trace

Concept Flow - Trapping Rain Water Problem

Input array of heights

↓

Calculate max left heights for each position

↓

Calculate max right heights for each position

↓

For each position: min(max_left, max_right) - height

↓

Sum all positive differences

↓

Output total trapped water

The flow shows how we find the water trapped at each position by comparing the tallest walls on left and right sides.

Execution Sample

DSA Python

heights = [0,1,0,2,1,0,1,3,2,1,2,1]
left_max = [0]*len(heights)
right_max = [0]*len(heights)
water = 0
for i in range(1, len(heights)):
    left_max[i] = max(left_max[i-1], heights[i-1])

This code calculates the maximum height to the left of each position.

Execution Table

Step	Operation	Index	left_max	right_max	Water Trapped at Index	Total Water	Visual State
1	Initialize left_max[0]	0	[0,0,0,0,0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	Heights: 0 1 0 2 1 0 1 3 2 1 2 1
2	Calculate left_max[1]	1	[0,0,0,0,0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	left_max updated at 1
3	Calculate left_max[2]	2	[0,1,1,0,0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	left_max updated at 2
4	Calculate left_max[3]	3	[0,1,1,1,0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	left_max updated at 3
5	Calculate left_max[4]	4	[0,1,1,2,2,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	left_max updated at 4
6	Calculate left_max[5]	5	[0,1,1,2,2,2,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	left_max updated at 5
7	Calculate left_max[6]	6	[0,1,1,2,2,2,2,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	left_max updated at 6
8	Calculate left_max[7]	7	[0,1,1,2,2,2,2,2,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	left_max updated at 7
9	Calculate left_max[8]	8	[0,1,1,2,2,2,2,3,3,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	left_max updated at 8
10	Calculate left_max[9]	9	[0,1,1,2,2,2,2,3,3,3,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	left_max updated at 9
11	Calculate left_max[10]	10	[0,1,1,2,2,2,2,3,3,3,3,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	left_max updated at 10
12	Calculate left_max[11]	11	[0,1,1,2,2,2,2,3,3,3,3,3]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	left_max updated at 11
13	Initialize right_max[last]	11	[0,1,1,2,2,2,2,3,3,3,3,3]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	right_max initialized at last index
14	Calculate right_max[10]	10	[0,1,1,2,2,2,2,3,3,3,3,3]	[1,0,0,0,0,0,0,0,0,0,0,0]	0	0	right_max updated at 10
15	Calculate right_max[9]	9	[0,1,1,2,2,2,2,3,3,3,3,3]	[2,1,0,0,0,0,0,0,0,0,0,0]	0	0	right_max updated at 9
16	Calculate right_max[8]	8	[0,1,1,2,2,2,2,3,3,3,3,3]	[2,2,1,0,0,0,0,0,0,0,0,0]	0	0	right_max updated at 8
17	Calculate right_max[7]	7	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,2,2,1,0,0,0,0,0,0,0,0]	0	0	right_max updated at 7
18	Calculate right_max[6]	6	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,2,2,1,0,0,0,0,0,0,0]	0	0	right_max updated at 6
19	Calculate right_max[5]	5	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,2,2,1,0,0,0,0,0,0]	0	0	right_max updated at 5
20	Calculate right_max[4]	4	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,2,2,1,0,0,0,0,0]	0	0	right_max updated at 4
21	Calculate right_max[3]	3	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,2,2,1,0,0,0,0]	0	0	right_max updated at 3
22	Calculate right_max[2]	2	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,2,2,1,0,0,0]	0	0	right_max updated at 2
23	Calculate right_max[1]	1	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,2,2,1,0,0]	0	0	right_max updated at 1
24	Calculate right_max[0]	0	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,2,2,1,0]	0	0	right_max updated at 0
25	Calculate water trapped at index 0	0	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,2,2,1,0]	0	0	Water trapped = min(0,3)-0=0
26	Calculate water trapped at index 1	1	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,2,2,1,0]	0	0	Water trapped = min(1,3)-1=0
27	Calculate water trapped at index 2	2	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,2,2,1,0]	1	1	Water trapped = min(1,3)-0=1
28	Calculate water trapped at index 3	3	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,2,2,1,0]	0	1	Water trapped = min(2,3)-2=0
29	Calculate water trapped at index 4	4	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,2,2,1,0]	1	2	Water trapped = min(2,3)-1=1
30	Calculate water trapped at index 5	5	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,2,2,1,0]	2	4	Water trapped = min(2,3)-0=2
31	Calculate water trapped at index 6	6	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,2,2,1,0]	1	5	Water trapped = min(2,3)-1=1
32	Calculate water trapped at index 7	7	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,2,2,1,0]	0	5	Water trapped = min(3,3)-3=0
33	Calculate water trapped at index 8	8	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,2,2,1,0]	0	5	Water trapped = min(3,2)-2=0
34	Calculate water trapped at index 9	9	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,2,2,1,0]	1	6	Water trapped = min(3,2)-1=1
35	Calculate water trapped at index 10	10	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,2,2,1,0]	0	6	Water trapped = min(3,1)-2=0
36	Calculate water trapped at index 11	11	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,2,2,1,0]	0	6	Water trapped = min(3,0)-1=0
37	Sum total trapped water	-	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,2,2,1,0]	-	6	Total trapped water = 6 units

💡 All indices processed, total trapped water calculated

Variable Tracker

Variable	Start	After Step 12	After Step 24	After Step 37
heights	[0,1,0,2,1,0,1,3,2,1,2,1]	[0,1,0,2,1,0,1,3,2,1,2,1]	[0,1,0,2,1,0,1,3,2,1,2,1]	[0,1,0,2,1,0,1,3,2,1,2,1]
left_max	[0,0,0,0,0,0,0,0,0,0,0,0]	[0,1,1,2,2,2,2,3,3,3,3,3]	[0,1,1,2,2,2,2,3,3,3,3,3]	[0,1,1,2,2,2,2,3,3,3,3,3]
right_max	[0,0,0,0,0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	[3,3,3,3,3,3,3,3,2,2,1,0]	[3,3,3,3,3,3,3,3,2,2,1,0]
water	0	0	0	6

Key Moments - 3 Insights

Why do we calculate left_max and right_max arrays before computing trapped water?

Because at each position, the water trapped depends on the tallest wall to the left and right. The execution_table rows 2-24 show how these arrays are built first to use in water calculation later.

Why do we subtract the height from min(left_max, right_max) to find trapped water?

Water can only be trapped up to the shorter wall between left and right. Subtracting the height gives the water level above the block. See execution_table rows 25-36 for this calculation.

Why do we ignore negative values when calculating trapped water?

If min(left_max, right_max) is less than or equal to height, no water is trapped (negative or zero). The code only adds positive differences, as shown in execution_table rows 27,29,30,31,34.

Visual Quiz - 3 Questions

Look at the execution_table at step 27, what is the water trapped at index 2?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'Water Trapped at Index' column at step 27 in execution_table

At which step does the total trapped water become 5 units?

A Step 30

B Step 31

C Step 32

D Step 33

💡 Hint

Look at the 'Total Water' column in execution_table rows 30 and 31

If the height at index 5 changed from 0 to 2, how would the trapped water at index 5 change?

A Increase

B Decrease

C Stay the same

D Become zero

💡 Hint

Refer to variable_tracker and execution_table rows 30 for water trapped at index 5

Concept Snapshot

Trapping Rain Water Problem:
- Input: array of heights representing walls
- Compute left_max and right_max arrays
- Water at index = max(0, min(left_max, right_max) - height)
- Sum water at all indices for total trapped water
- Time: O(n), Space: O(n)

Full Transcript

The Trapping Rain Water problem finds how much water can be trapped between walls of different heights. We first calculate the maximum height to the left and right of each position. Then, for each position, the water trapped is the difference between the smaller of these two max heights and the current height, if positive. Summing these values gives the total trapped water. The execution table shows step-by-step how left_max and right_max arrays are built, then how water trapped at each index is calculated and summed. Key moments clarify why these arrays are needed and why negative water values are ignored.

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