Why Trapping Rain Water Using Stack in DSA Python?

The Big Idea

Discover how a simple stack can solve a tricky water-trapping puzzle faster than you think!

The Scenario

Imagine you have a row of buildings with different heights after a rainstorm. You want to find out how much water is trapped between these buildings. Doing this by checking every possible pair of buildings manually is like trying to count water drops one by one--it's slow and confusing.

The Problem

Manually checking each pair of buildings to calculate trapped water means repeating many steps and missing some tricky spots. It's easy to make mistakes, and the process takes too long when there are many buildings.

The Solution

Using a stack helps keep track of building heights in a smart way. It lets you quickly find where water can be trapped by remembering the last building heights and calculating trapped water as you go. This method is faster and less error-prone.

Before vs After

✗ Before

water = 0
for i in range(len(heights)):
    for j in range(i+1, len(heights)):
        # check and calculate trapped water manually

✓ After

stack = []
water = 0
for current_index, height in enumerate(heights):
    while stack and height > heights[stack[-1]]:
        # calculate trapped water using stack

What It Enables

This method enables fast and accurate calculation of trapped rainwater even for large sets of buildings.

Real Life Example

City planners can use this to estimate how much rainwater will collect between buildings to design better drainage systems.

Key Takeaways

Manual checking is slow and error-prone.

Stack helps track building heights efficiently.

Calculates trapped water quickly and correctly.

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