Why Trapping Rain Water Using Stack in DSA C?

The Big Idea

Discover how a simple stack can solve a tricky rainwater puzzle faster than guessing!

The Scenario

Imagine you have a row of buildings with different heights, and after it rains, you want to find out how much water gets trapped between them. Doing this by looking at each building and guessing the water trapped is like trying to count raindrops one by one on a big roof -- slow and confusing.

The Problem

Manually checking each building and comparing it with every other building to find trapped water takes a lot of time and can easily lead to mistakes. It's like trying to solve a puzzle by testing every piece with every other piece -- it quickly becomes overwhelming and error-prone.

The Solution

Using a stack helps us keep track of buildings in a smart way. We can quickly find where water can be trapped by remembering the heights and positions of buildings we have seen. This method is faster and less confusing, like having a helper who points out where water will collect as you walk along the buildings.

Before vs After

✗ Before

int trappedWater(int heights[], int size) {
    int water = 0;
    for (int i = 1; i < size - 1; i++) {
        int maxLeft = 0, maxRight = 0;
        for (int j = i; j >= 0; j--) maxLeft = (maxLeft > heights[j]) ? maxLeft : heights[j];
        for (int j = i; j < size; j++) maxRight = (maxRight > heights[j]) ? maxRight : heights[j];
        water += (maxLeft < maxRight ? maxLeft : maxRight) - heights[i];
    }
    return water;
}

✓ After

int trappedWater(int heights[], int size) {
    int water = 0, top, current = 0;
    int stack[size];
    int stackTop = -1;
    while (current < size) {
        while (stackTop != -1 && heights[current] > heights[stack[stackTop]]) {
            top = stack[stackTop--];
            if (stackTop == -1) break;
            int distance = current - stack[stackTop] - 1;
            int bounded_height = (heights[current] < heights[stack[stackTop]] ? heights[current] : heights[stack[stackTop]]) - heights[top];
            water += distance * bounded_height;
        }
        stack[++stackTop] = current++;
    }
    return water;
}

What It Enables

This method lets us quickly and accurately calculate trapped rainwater in complex building arrangements, saving time and avoiding mistakes.

Real Life Example

City planners use this idea to understand how water collects between buildings after rain, helping them design better drainage systems to prevent flooding.

Key Takeaways

Manual checking is slow and error-prone for trapping rainwater.

Stack helps track building heights efficiently to find trapped water.

This approach speeds up calculations and reduces mistakes.