Trapping Rain Water Using Stack in DSA C

Mental Model

We use a stack to keep track of bars that can trap water when a taller bar appears on the right side.

Analogy: Imagine pouring water between buildings of different heights; water gets trapped in valleys between taller buildings.

Height array: [0,1,0,2,1,0,1,3,2,1,2,1]
Stack stores indices of bars that form boundaries for trapped water.

Initial:
Index: 0 1 2 3 4 5 6 7 8 9 10 11
Height:0 1 0 2 1 0 1 3 2 1  2  1
Stack: empty
Water trapped: 0

Dry Run Walkthrough

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Goal: Calculate total water trapped between bars using a stack

Step 1: Push index 0 (height 0) onto stack

Stack: [0]
Water trapped: 0

Why: Start with first bar as potential boundary

Step 2: Push index 1 (height 1) onto stack since height[1] > height[0]

Stack: [0,1]
Water trapped: 0

Why: Current bar taller, so push to find right boundary later

Step 3: Push index 2 (height 0) onto stack since height[2] < height[1]

Stack: [0,1,2]
Water trapped: 0

Why: Lower bar may trap water later

Step 4: At index 3 (height 2), pop index 2 (height 0) from stack; calculate trapped water between index 1 and 3

Stack after pop: [0,1]
Calculate distance=3-1-1=1
Bounded height=min(2,1)-0=1
Water trapped += 1*1=1
Water trapped: 1

Why: Found right boundary taller than middle bar, so water trapped here

Step 5: Pop index 1 (height 1) since height[3]=2 > height[1]=1; calculate trapped water between index 0 and 3

Stack after pop: [0]
Distance=3-0-1=2
Bounded height=min(2,0)-1= -1 (negative, so 0)
Water trapped: 1

Why: No water trapped here because left boundary is lower

Step 6: Push index 3 (height 2) onto stack

Stack: [0,3]
Water trapped: 1

Why: Current bar becomes new boundary

Step 7: Push index 4 (height 1) onto stack since height[4]<height[3]

Stack: [0,3,4]
Water trapped: 1

Why: Lower bar may trap water later

Step 8: Push index 5 (height 0) onto stack since height[5]<height[4]

Stack: [0,3,4,5]
Water trapped: 1

Why: Lower bar may trap water later

Step 9: At index 6 (height 1), pop index 5 (height 0); calculate trapped water between index 4 and 6

Stack after pop: [0,3,4]
Distance=6-4-1=1
Bounded height=min(1,1)-0=1
Water trapped += 1*1=1
Water trapped: 2

Why: Water trapped in the valley formed by bars at 4 and 6

Step 10: Height[6]=1 equals height[4]=1, pop index 4 (height 1) and push index 6

Stack after pop: [0,3]
Push 6
Stack: [0,3,6]
Water trapped: 2

Why: Replace boundary with current bar of same height

Step 11: At index 7 (height 3), pop index 6 (height 1); calculate trapped water between index 3 and 7

Stack after pop: [0,3]
Distance=7-3-1=3
Bounded height=min(3,2)-1=1
Water trapped += 3*1=3
Water trapped: 5

Why: Water trapped in valley between bars at 3 and 7

Step 12: Pop index 3 (height 2) since height[7]=3 > height[3]=2; push index 7

Stack after pop: [0]
Push 7
Stack: [0,7]
Water trapped: 5

Why: Update boundary to taller bar

Step 13: Push index 8 (height 2) since height[8]<height[7]

Stack: [0,7,8]
Water trapped: 5

Why: Lower bar may trap water later

Step 14: Push index 9 (height 1) since height[9]<height[8]

Stack: [0,7,8,9]
Water trapped: 5

Why: Lower bar may trap water later

Step 15: At index 10 (height 2), pop index 9 (height 1); calculate trapped water between index 8 and 10

Stack after pop: [0,7,8]
Distance=10-8-1=1
Bounded height=min(2,2)-1=1
Water trapped += 1*1=1
Water trapped: 6

Why: Water trapped in valley between bars at 8 and 10

Step 16: Pop index 8 (height 2) since height[10]=2 equals height[8]=2; push index 10

Stack after pop: [0,7]
Push 10
Stack: [0,7,10]
Water trapped: 6

Why: Replace boundary with current bar of same height

Step 17: Push index 11 (height 1) since height[11]<height[10]

Stack: [0,7,10,11]
Water trapped: 6

Why: Lower bar may trap water later

Result:

Stack: [0,7,10,11]
Total water trapped: 6

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Stack structure to hold indices
typedef struct Stack {
    int *arr;
    int top;
    int capacity;
} Stack;

Stack* createStack(int capacity) {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->arr = (int*)malloc(capacity * sizeof(int));
    return stack;
}

int isEmpty(Stack *stack) {
    return stack->top == -1;
}

void push(Stack *stack, int val) {
    stack->arr[++stack->top] = val;
}

int pop(Stack *stack) {
    return stack->arr[stack->top--];
}

int peek(Stack *stack) {
    return stack->arr[stack->top];
}

int trap(int* height, int heightSize) {
    Stack *stack = createStack(heightSize);
    int water = 0;
    int i = 0;

    while (i < heightSize) {
        // While current bar is higher than top of stack bar
        while (!isEmpty(stack) && height[i] > height[peek(stack)]) {
            int top = pop(stack); // middle bar
            if (isEmpty(stack))
                break; // no left boundary

            int distance = i - peek(stack) - 1; // width between boundaries
            int bounded_height = (height[i] < height[peek(stack)] ? height[i] : height[peek(stack)]) - height[top];
            if (bounded_height > 0) {
                water += distance * bounded_height;
            }
        }
        push(stack, i);
        i++;
    }

    free(stack->arr);
    free(stack);
    return water;
}

int main() {
    int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
    int size = sizeof(height)/sizeof(height[0]);
    int result = trap(height, size);
    printf("Total water trapped: %d\n", result);
    return 0;
}

while (i < heightSize) {

iterate over each bar to process trapping

while (!isEmpty(stack) && height[i] > height[peek(stack)]) {

pop bars lower than current to calculate trapped water

int top = pop(stack);

remove middle bar to calculate trapped water

if (isEmpty(stack)) break;

no left boundary means no trapped water here

int distance = i - peek(stack) - 1;

calculate width between left and right boundaries

int bounded_height = (height[i] < height[peek(stack)] ? height[i] : height[peek(stack)]) - height[top];

calculate effective height of trapped water

water += distance * bounded_height;

add trapped water volume for this segment

push(stack, i);

push current bar index as new boundary

Output

Total water trapped: 6

Complexity Analysis

Time: O(n) because each bar is pushed and popped at most once

Space: O(n) for the stack that stores indices of bars

vs Alternative: Compared to brute force O(n^2) checking left and right max for each bar, stack approach is more efficient

Edge Cases

Empty height array

Returns 0 as no bars to trap water

DSA C

while (i < heightSize) {

All bars of same height

No water trapped, returns 0

DSA C

while (!isEmpty(stack) && height[i] > height[peek(stack)]) {

Strictly increasing heights

No water trapped, returns 0

DSA C

while (!isEmpty(stack) && height[i] > height[peek(stack)]) {

When to Use This Pattern

When you need to find trapped water between bars or heights, use a stack to track boundaries and calculate trapped water efficiently.

Common Mistakes

Mistake: Not checking if stack is empty before accessing top, causing errors
Fix: Always check if stack is empty before popping or peeking

Mistake: Calculating trapped water with wrong distance or height leading to negative or incorrect values
Fix: Use correct formula: distance = current_index - left_boundary_index - 1; bounded_height = min(left_height, right_height) - middle_height

Summary

Calculates total trapped rain water between bars using a stack to find boundaries.

Use when you want an efficient O(n) solution to the trapping rain water problem.

The key insight is to use a stack to find left and right boundaries and calculate trapped water when a taller bar appears.