Trapping Rain Water Using Stack in DSA Python - Build from Scratch

Trapping Rain Water Using Stack

📖 Scenario: Imagine you have a row of walls of different heights. When it rains, water gets trapped between these walls. You want to find out how much water is trapped after the rain.This is like looking at a city skyline after rain and measuring the water pools between buildings.

🎯 Goal: You will write a program to calculate the total amount of trapped rain water using a stack data structure.

📋 What You'll Learn

Create a list called heights with exact values representing wall heights

Create an empty list called stack to use as a stack

Use a for loop with variable i to iterate over heights

Implement the logic to calculate trapped water using the stack

Print the total trapped water as an integer

💡 Why This Matters

🌍 Real World

Calculating trapped rain water helps in urban planning and drainage system design.

💼 Career

Understanding stack usage and problem-solving with data structures is essential for software engineering roles.

1

Create the wall heights list

Create a list called heights with these exact values: [0,1,0,2,1,0,1,3,2,1,2,1]

DSA Python

# Create the list heights with given wall heights
# Your code here

Hint

Use square brackets to create the list and separate numbers with commas.

2

Initialize the stack and total water counter

Create an empty list called stack and a variable water set to 0

DSA Python

heights = [0,1,0,2,1,0,1,3,2,1,2,1]
# Create an empty list stack and set water to 0
# Your code here

Hint

Use [] to create an empty list and assign 0 to water.

3

Calculate trapped water using stack

Use a for loop with variable i to iterate over range(len(heights)). Inside the loop, use a while loop to check if stack is not empty and heights[i] is greater than heights[stack[-1]]. Pop the top of the stack into top. If stack becomes empty, break. Calculate the distance as i - stack[-1] - 1 and bounded height as min(heights[i], heights[stack[-1]]) - heights[top]. Add distance * bounded_height to water. After the while loop, append i to stack.

DSA Python

heights = [0,1,0,2,1,0,1,3,2,1,2,1]
stack = []
water = 0
# Use a for loop with i in range(len(heights)) to calculate trapped water
# Your code here

Hint

Use a stack to keep indexes of walls. Calculate trapped water when current wall is taller than the wall at stack top.

4

Print the total trapped water

Write print(water) to display the total trapped rain water.

DSA Python

heights = [0,1,0,2,1,0,1,3,2,1,2,1]
stack = []
water = 0
for i in range(len(heights)):
    while stack and heights[i] > heights[stack[-1]]:
        top = stack.pop()
        if not stack:
            break
        distance = i - stack[-1] - 1
        bounded_height = min(heights[i], heights[stack[-1]]) - heights[top]
        water += distance * bounded_height
    stack.append(i)
# Print the total trapped water
# Your code here

Hint

Use print to show the final trapped water amount.

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