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.

Practice

1. What is the main purpose of using a stack in the Trapping Rain Water Using Stack algorithm?

easy

A. To store the total amount of trapped water

B. To sort the heights of bars in ascending order

C. To keep track of bars that are not yet processed for water trapping

D. To reverse the order of the height array

Solution

1. Step 1: Understand the role of the stack

   The stack stores indices of bars that are waiting to find a right boundary to trap water.

2. Step 2: Why not other options?

   The stack does not store water amount or sort bars; it helps find boundaries for trapped water.

3. Final Answer:

   To keep track of bars that are not yet processed for water trapping -> Option C

4. Quick Check:

   Stack tracks bars for trapping water = B [OK]

Hint: Stack holds bars waiting for right boundary [OK]

Common Mistakes:

• Thinking stack stores water amount
• Assuming stack sorts the bars
• Believing stack reverses the array

2. Which of the following Python code snippets correctly initializes an empty stack for the trapping rain water algorithm?

easy

A. stack = 0

B. stack = {}

C. stack = None

D. stack = []

Solution

1. Step 1: Identify correct stack initialization

   In Python, a stack is commonly represented by a list, so stack = [] initializes an empty stack.

2. Step 2: Why other options are wrong

   {} is a dictionary, None is no value, and 0 is an integer, none suitable for stack operations.

3. Final Answer:

   stack = [] -> Option D

4. Quick Check:

   Empty list for stack = A [OK]

Hint: Use empty list [] to create stack in Python [OK]

Common Mistakes:

• Using {} which creates a dictionary
• Assigning None instead of list
• Using integer 0 as stack

3. What is the output of the following code snippet that uses stack to calculate trapped rain water?

def trap(height):
    stack = []
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            top = stack.pop()
            if not stack:
                break
            distance = i - stack[-1] - 1
            bounded_height = min(height[stack[-1]], h) - height[top]
            water += distance * bounded_height
        stack.append(i)
    return water

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

medium

A. 6

B. 5

C. 4

D. 7

Solution

1. Step 1: Trace the algorithm with given heights

   The code calculates trapped water for heights [0,1,0,2,1,0,1,3,2,1,2,1]. The total trapped water is 6 units.

2. Step 2: Confirm calculation matches known example

   This is a classic example where trapped water is 6, matching the output of the code.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Trapped water = 6 [OK]

Hint: Classic example trap water = 6 units [OK]

Common Mistakes:

• Miscounting trapped water units
• Ignoring stack pop conditions
• Wrong distance or bounded height calculation

4. Identify the error in the following code snippet for trapping rain water using stack:

def trap(height):
    stack = []
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] <= h:
            top = stack.pop()
            if not stack:
                break
            distance = i - stack[-1] - 1
            bounded_height = min(height[stack[-1]], h) - height[top]
            water += distance * bounded_height
        stack.append(i)
    return water

print(trap([4,2,0,3,2,5]))

medium

A. The distance calculation is incorrect

B. The condition should be < instead of <=

C. The stack should be a queue

D. The water variable should be initialized to 1

Solution

1. Step 1: Check the while loop condition

   The condition height[stack[-1]] <= h causes popping even when heights are equal, which is incorrect for trapping water calculation.

2. Step 2: Correct condition and reason

   It should be height[stack[-1]] < h to pop only when current height is strictly greater, ensuring correct water trapping.

3. Final Answer:

   The condition should be < instead of <= -> Option B

4. Quick Check:

   Use < not <= in while condition [OK]

Hint: Use strict less than < in stack pop condition [OK]

Common Mistakes:

• Using <= causes wrong popping
• Confusing stack with queue
• Incorrect distance formula
• Initializing water to 1 instead of 0

5. Given the height array [3, 0, 2, 0, 4], what is the total trapped rain water calculated using the stack method? Explain how the stack helps in this calculation.

hard

A. 4

B. 7

C. 5

D. 6

Solution

1. Step 1: Calculate trapped water step-by-step

   Heights: [3,0,2,0,4]. Water trapped at position 1 is 3 units, at position 2 is 0 units, at position 3 is 1 unit. Total trapped water = 4 units.

2. Step 2: Explain stack role in calculation

   The stack stores indices of bars. When a higher bar is found, it pops lower bars and calculates trapped water using distance and bounded height between bars.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Stack helps find boundaries; trapped water = 4 [OK]

Hint: Stack finds left/right boundaries to calculate trapped water [OK]

Common Mistakes:

• Adding trapped water incorrectly
• Ignoring zero height bars
• Not using stack to find boundaries