Trapping Rain Water Problem in DSA Python - Build from Scratch

Trapping Rain Water Problem

📖 Scenario: Imagine a street with buildings of different heights. When it rains, water gets trapped between these buildings. We want to find out how much water is trapped after the rain stops.

🎯 Goal: Build a program that calculates the total amount of water trapped between buildings represented by their heights.

📋 What You'll Learn

Create a list called heights with exact building heights

Create two lists called left_max and right_max to store maximum heights from left and right

Use a loop to fill left_max and right_max

Calculate trapped water using the minimum of left_max and right_max for each building

Print the total trapped water

💡 Why This Matters

🌍 Real World

This problem models how water collects in valleys between buildings or hills, useful in urban planning and flood prediction.

💼 Career

Understanding this problem helps in software roles involving algorithms, problem solving, and optimization.

1

Create the building heights list

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

DSA Python

# Create the list of building heights
# Your code here

Hint

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

2

Create left_max and right_max lists

Create two lists called left_max and right_max with the same length as heights, filled with zeros

DSA Python

heights = [0, 2, 0, 3, 0, 1, 0, 4, 0, 2]
# Create left_max and right_max lists filled with zeros
# Your code here

Hint

Use len(heights) to get the length and multiply a list with zero to create the lists.

3

Fill left_max and right_max lists

Use a for loop with variable i from 1 to len(heights) - 1 to fill left_max where each element is the maximum of left_max[i-1] and heights[i-1]. Then use a for loop with variable i from len(heights) - 2 down to 0 to fill right_max where each element is the maximum of right_max[i+1] and heights[i+1].

DSA Python

heights = [0, 2, 0, 3, 0, 1, 0, 4, 0, 2]
left_max = [0] * len(heights)
right_max = [0] * len(heights)
# Fill left_max and right_max lists using for loops
# Your code here

Hint

Use range with start, stop, and step to loop forward and backward.

4

Calculate and print total trapped water

Create a variable called total_water and set it to 0. Use a for loop with variable i from 0 to len(heights) - 1 to add to total_water the difference between the minimum of left_max[i] and right_max[i] and heights[i]. Then print total_water.

DSA Python

heights = [0, 2, 0, 3, 0, 1, 0, 4, 0, 2]
left_max = [0] * len(heights)
right_max = [0] * len(heights)

for i in range(1, len(heights)):
    left_max[i] = max(left_max[i-1], heights[i-1])

for i in range(len(heights) - 2, -1, -1):
    right_max[i] = max(right_max[i+1], heights[i+1])

# Calculate total trapped water and print it
# Your code here

Hint

Use min to find the smaller of two values and add the difference only if it is positive.