Trapping Rain Water Using Stack in DSA Python - Execution Trace

Concept Flow - Trapping Rain Water Using Stack

Start with empty stack

↓

Iterate over height array

↓

While stack not empty and current height > height at stack top

↓

Pop top

↓

Calculate distance and bounded height

↓

Add trapped water

↓

Push current index to stack

↓

Repeat until end

↓

Return total trapped water

We use a stack to keep indices of bars. When current bar is higher than stack top, we pop and calculate trapped water between bars.

Execution Sample

DSA Python

height = [0,1,0,2,1,0,1,3,2,1,2,1]
stack = []
water = 0
for i in range(len(height)):
    while stack and height[i] > height[stack[-1]]:
        top = stack.pop()

This code iterates over the height array, using a stack to find trapped water by popping lower bars when a higher bar is found.

Execution Table

Step	Operation	Stack (indices)	Popped Index	Distance	Bounded Height	Water Added	Total Water	Visual State (height bars with trapped water)
1	Push index 0	[0]	None	N/A	N/A	0	0	0(0) 1( ) 0( ) 2( ) 1( ) 0( ) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
2	Push index 1	[0,1]	None	N/A	N/A	0	0	0(0) 1( ) 0( ) 2( ) 1( ) 0( ) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
3	Pop index 1 (height=1) because 0 < 1	[0]	1	N/A	N/A	0	0	0(0) 1( ) 0( ) 2( ) 1( ) 0( ) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
3	Push index 2	[0,2]	None	N/A	N/A	0	0	0(0) 1( ) 0( ) 2( ) 1( ) 0( ) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
4	Pop index 2 (height=0) because 2 > 0	[0]	2	1	min(1,2)-0=1	1	1	0(0) 1( ) 0(1) 2( ) 1( ) 0( ) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
4	Push index 3	[0,3]	None	N/A	N/A	0	1	0(0) 1( ) 0(1) 2( ) 1( ) 0( ) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
5	Push index 4	[0,3,4]	None	N/A	N/A	0	1	0(0) 1( ) 0(1) 2( ) 1( ) 0( ) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
6	Pop index 4 (height=1) because 3 > 1	[0,3]	4	N/A	N/A	0	1	0(0) 1( ) 0(1) 2( ) 1( ) 0( ) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
6	Push index 5	[0,3,5]	None	N/A	N/A	0	1	0(0) 1( ) 0(1) 2( ) 1( ) 0( ) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
7	Pop index 5 (height=0) because 3 > 0	[0,3]	5	1	min(1,2)-0=1	1	2	0(0) 1( ) 0(1) 2( ) 1( ) 0(1) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
7	Push index 6	[0,3,6]	None	N/A	N/A	0	2	0(0) 1( ) 0(1) 2( ) 1( ) 0(1) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
8	Pop index 6 (height=1) because 3 > 1	[0,3]	6	N/A	N/A	0	2	0(0) 1( ) 0(1) 2( ) 1( ) 0(1) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
8	Push index 7	[0,3,7]	None	N/A	N/A	0	2	0(0) 1( ) 0(1) 2( ) 1( ) 0(1) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
9	No pop because stack top height=2 < 3	[0,3,7]	None	N/A	N/A	0	2	0(0) 1( ) 0(1) 2( ) 1( ) 0(1) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
10	Pop index 7 (height=3) because 8 > 2	[0,3]	7	4	min(2,3)-2=0	0	2	0(0) 1( ) 0(1) 2( ) 1( ) 0(1) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
10	Push index 8	[0,3,8]	None	N/A	N/A	0	2	0(0) 1( ) 0(1) 2( ) 1( ) 0(1) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
11	Pop index 8 (height=2) because 9 > 1	[0,3]	8	1	min(1,2)-1=0	0	2	0(0) 1( ) 0(1) 2( ) 1( ) 0(1) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
11	Push index 9	[0,3,9]	None	N/A	N/A	0	2	0(0) 1( ) 0(1) 2( ) 1( ) 0(1) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
12	No pop because 2 > 1	[0,3,9]	None	N/A	N/A	0	2	0(0) 1( ) 0(1) 2( ) 1( ) 0(1) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
13	Push index 10	[0,3,9,10]	None	N/A	N/A	0	2	0(0) 1( ) 0(1) 2( ) 1( ) 0(1) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
14	Pop index 10 (height=2) because 11 > 1	[0,3,9]	10	1	min(1,2)-1=0	0	2	0(0) 1( ) 0(1) 2( ) 1( ) 0(1) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )
14	Push index 11	[0,3,9,11]	None	N/A	N/A	0	2	0(0) 1( ) 0(1) 2( ) 1( ) 0(1) 1( ) 3( ) 2( ) 1( ) 2( ) 1( )

💡 Reached end of height array, total trapped water = 6

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 7	After Step 10	After Step 14	Final
stack	[]	[0]	[0,3]	[0,3]	[0,3,8]	[0,3,9,11]	[0,3,9,11]
water	0	0	2	2	2	2	6
i	0	1	5	8	10	11	12

Key Moments - 3 Insights

Why do we pop from the stack only when current height is greater than height at stack top?

Because popping happens only when we find a right boundary taller than the bar at stack top, allowing us to trap water between them. See execution_table rows 4 and 7 where popping occurs when current height is higher.

How is the trapped water amount calculated after popping?

We calculate distance between current index and new stack top minus one, then multiply by bounded height (minimum of current and stack top heights minus popped bar height). Refer to execution_table rows 4 and 7 for distance and bounded height calculations.

Why do we push the current index after popping?

After popping lower bars, we push current index to mark a new boundary for future trapping. This is shown in execution_table rows after popping steps, e.g., step 4 and 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the water added after popping index 2?

A 1

B 0

C 2

D 3

💡 Hint

Check the 'Water Added' column at step 4 in execution_table.

At which step does the total trapped water first become 2?

A Step 4

B Step 7

C Step 10

D Step 14

💡 Hint

Look at the 'Total Water' column in execution_table and find when it reaches 2.

If the height at index 5 was increased to 2, how would the water trapped change at step 7?

A Water added would stay the same

B Water added would decrease

C Water added would increase

D No water would be trapped

💡 Hint

Consider how a taller bar at index 5 affects popping and bounded height at step 7.

Concept Snapshot

Trapping Rain Water Using Stack:
- Use a stack to store indices of bars.
- Iterate over heights, pop when current bar is taller than stack top.
- Calculate trapped water using distance and bounded height.
- Push current index after popping.
- Sum all trapped water and return total.

Full Transcript

This visualization shows how to trap rain water using a stack. We start with an empty stack and iterate over the height array. When the current height is greater than the height at the top of the stack, we pop from the stack and calculate trapped water between the bars. The trapped water is calculated by finding the distance between the current index and the new top of the stack minus one, multiplied by the bounded height which is the minimum of the current height and the height at the new top minus the popped height. We add this trapped water to the total. After popping, we push the current index to the stack to mark a new boundary. This process continues until we reach the end of the array. The total trapped water is then returned. The execution table tracks each step, showing stack changes, popped indices, distance, bounded height, water added, and the total water trapped so far. The variable tracker shows how the stack, water, and index variables change over time. Key moments clarify why popping happens only when current height is greater, how trapped water is calculated, and why pushing happens after popping. The quiz questions test understanding of water added at specific steps, when total water reaches certain values, and how changes in height affect trapped water.