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.