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.