Trapping Rain Water Using Stack in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trapping Rain Water Calculation

What is the output of the following Python code that calculates trapped rain water using a stack?

DSA Python

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]))

A 6

B 5

C 8

D 7

💡 Hint

Think about how the stack helps find boundaries to trap water between bars.

The code uses a stack to track indices of bars. When a higher bar is found, it calculates trapped water between the current bar and the last bar in the stack. The total trapped water for the input is 6 units.

🧠 Conceptual

intermediate

Understanding Stack Usage in Trapping Rain Water

Why do we use a stack in the trapping rain water problem?

A To sort the bars by height

B To store the amount of water trapped at each index

C To keep track of indices of bars that are not yet bounded by a higher bar on the right

D To reverse the order of the bars

💡 Hint

Think about how the stack helps find boundaries for trapping water.

The stack stores indices of bars that have not yet found a higher bar on the right side. When a higher bar appears, it helps calculate trapped water between bars.

🔧 Debug

advanced

Identify the Error in Trapping Rain Water Code

What error will this code raise when executed?

DSA Python

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]))

A Infinite loop

B IndexError due to empty stack access

C TypeError due to invalid operation

D No error, output is 9

💡 Hint

Check the condition in the while loop carefully.

The code uses <= in the while condition, which still works correctly and does not cause errors. The output for the input is 9 units of trapped water.

❓ Predict Output

advanced

Output of Modified Trapping Rain Water Code

What is the output of this modified trapping rain water code?

DSA Python

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]
            if bounded_height > 0:
                water += distance * bounded_height
        stack.append(i)
    return water

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

A 10

B 9

C 8

D 7

💡 Hint

The added check prevents adding negative water amounts.

The added if condition avoids adding negative trapped water. The total trapped water remains 9 units for the input.

🚀 Application

expert

Maximum Water Trapped in Large Histogram

Given a histogram with heights [5,2,1,2,1,5,3,2,4,1], what is the maximum amount of water trapped using the stack method?

A 14

B 15

C 13

D 12

💡 Hint

Visualize the bars and trapped water between the highest boundaries.

The maximum trapped water calculated by the stack method for the given heights is 14 units.