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.