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.

Practice

1. What is the main purpose of using a stack in the Trapping Rain Water Using Stack algorithm?

easy

A. To reverse the order of the bars

B. To store the total amount of trapped water directly

C. To sort the heights of bars in ascending order

D. To keep track of bars that are not yet processed for water trapping

Solution

1. Step 1: Understand stack role in the algorithm

   The stack stores indices of bars that are waiting to find a right boundary to trap water.

2. Step 2: Clarify what the stack does not do

   The stack does not store water amounts 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 D

4. Quick Check:

   Stack tracks bars for trapping water [OK]

Hint: Stack holds indices of bars waiting for right boundary [OK]

Common Mistakes:

• Thinking stack stores water volume directly
• Assuming stack sorts the bars
• Believing stack reverses bar order

2. Which of the following C code snippets correctly declares a stack to store indices for trapping rain water?

easy

A. int stack[100]; int top = -1;

B. int stack; int top = 0;

C. int *stack = NULL; int top = 1;

D. int stack[] = {}; int top = -1;

Solution

1. Step 1: Check stack declaration syntax

   int stack[100]; int top = -1; declares an integer array with fixed size and initializes top to -1, which is correct for stack implementation.

2. Step 2: Identify incorrect declarations

   Options B, C, and D have wrong types or invalid initializations for stack and top pointer.

3. Final Answer:

   int stack[100]; int top = -1; -> Option A

4. Quick Check:

   Array + top = -1 is correct stack setup [OK]

Hint: Use array and top = -1 for empty stack [OK]

Common Mistakes:

• Using uninitialized or wrong top value
• Declaring stack as single int instead of array
• Using empty array syntax invalid in C

3. What is the output of the following code snippet that calculates trapped rain water using stack?

int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
int n = 12;
// Assume correct trapping rain water stack code runs here
int trapped = trappingRainWater(height, n);
printf("%d\n", trapped);

medium

A. 5

B. 6

C. 4

D. 7

Solution

1. Step 1: Understand the input heights

   The array represents bar heights where water can be trapped between taller bars.

2. Step 2: Calculate trapped water manually or recall known result

   The known trapped water for this input is 6 units.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Standard example trapped water = 6 [OK]

Hint: Remember classic example traps 6 units water [OK]

Common Mistakes:

• Miscounting trapped water units
• Confusing indexes or heights
• Assuming output is sum of heights

4. Identify the bug in this snippet of the trapping rain water stack algorithm:

while (top != -1 && height[i] > height[stack[top]]) {
  int topIndex = stack[top--];
  int distance = i - stack[top] - 1;
  int bounded_height = min(height[i], height[stack[top]]) - height[topIndex];
  water += distance * bounded_height;
}

medium

A. Using 'min' function without including its definition or header

B. Incorrect calculation of 'distance' by missing parentheses

C. Wrong decrement of 'top' causing stack underflow

D. Using 'water' variable without initialization

Solution

1. Step 1: Check function usage

   The code uses 'min' function but C standard library does not have 'min' by default; it needs a macro or function definition.

2. Step 2: Verify other parts

   Distance calculation and top decrement are correct; water variable usage depends on context but usually initialized.

3. Final Answer:

   Using 'min' function without including its definition or header -> Option A

4. Quick Check:

   min() undefined in C without custom code [OK]

Hint: Remember C needs custom min function or macro [OK]

Common Mistakes:

• Assuming min() is built-in in C
• Miscalculating distance with wrong parentheses
• Forgetting to initialize water variable

5. Given the heights array {4, 2, 0, 3, 2, 5}, what is the total trapped rain water calculated using the stack method?

hard

A. 8

B. 7

C. 9

D. 6

Solution

1. Step 1: Analyze the heights for trapped water

   Water trapped at each position i is max(0, min(left_max[i], right_max[i]) - height[i]), where left_max is tallest bar strictly to the left, right_max strictly to the right. Stack method yields same result.

2. Step 2: Calculate trapped water step-by-step

   - i=1: min(4,5)-2 = 2
   - i=2: min(4,5)-0 = 4
   - i=3: min(4,5)-3 = 1
   - i=4: min(4,5)-2 = 2
   Total: 2+4+1+2 = 9 units.

3. Final Answer:

   9 -> Option C

4. Quick Check:

   Total trapped water = 9 [OK]

Hint: Sum water trapped between boundaries carefully [OK]

Common Mistakes:

• Double counting trapped water
• Ignoring zero height bars
• Misidentifying boundaries