Trapping Rain Water Using Stack in DSA C#

Mental Model

We use a stack to remember bars that might trap water when a taller bar comes after them. The stack helps find boundaries to hold water between bars.

Analogy: Imagine a row of walls of different heights. When rain falls, water collects in dips between taller walls. The stack helps us find these walls quickly to measure trapped water.

Height bars: 0 1 0 2 1 0 1 3 2 1 2 1
Stack stores indices of bars that might trap water ->
[ ] ← empty stack
Bars: 0 -> 1 -> 0 -> 2 -> 1 -> 0 -> 1 -> 3 -> 2 -> 1 -> 2 -> 1 -> null

Dry Run Walkthrough

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

Goal: Calculate total water trapped between bars after raining

Step 1: i=0, Push index 0 (height 0) onto stack

Stack: [0]

Why: Start with first bar as potential boundary

Step 2: i=1 height 1 > top height[0]=0, pop 0 (stack empty, break), push 1

Stack: [1]
Total water: 0

Why: Pop shorter bar, no left boundary so no water trapped, push current as new boundary

Step 3: i=2 height 0 < top height[1]=1, push 2

Stack: [1,2]

Why: Lower bar, possible valley

Step 4: i=3 height 2 > top height[2]=0, pop 2 Calc: dist=3-1-1=1, bh=min(2,1)-0=1, water+=1 (total=1) still 2 > height[1]=1, pop 1 (stack empty, break) Push 3

Stack: [3]
Total water: 1

Why: Found right boundary (3), trapped 1 unit over bar 2 (between 1 and 3); popped 1 but no left boundary

Step 5: i=4 height 1 < top height[3]=2, push 4

Stack: [3,4]

Why: Lower bar, possible valley

Step 6: i=5 height 0 < top height[4]=1, push 5

Stack: [3,4,5]

Why: Lower bar, possible valley

Step 7: i=6 height 1 > top height[5]=0, pop 5 Calc: dist=6-4-1=1, bh=min(1,1)-0=1, water+=1 (total=2) 1 == height[4]=1 (not >), push 6

Stack: [3,4,6]
Total water: 2

Why: Found right boundary (6), trapped 1 unit over bar 5 (between 4 and 6)

Step 8: i=7 height 3 > top height[6]=1, pop 6 Calc: dist=7-4-1=2, bh=min(3,1)-1=0, water unchanged (total=2) still 3 > height[4]=1, pop 4 Calc: dist=7-3-1=3, bh=min(3,2)-1=1, water+=3 (total=5) still 3 > height[3]=2, pop 3 (stack empty, break) Push 7

Stack: [7]
Total water: 5

Why: Multiple pops: no water over 6 (height matches left), 3 units over 4 and 5 (between 3 and 7); popped 3 but no left

Step 9: i=8 height 2 < top height[7]=3, push 8

Stack: [7,8]

Why: Lower bar, possible valley

Step 10: i=9 height 1 < top height[8]=2, push 9

Stack: [7,8,9]

Why: Lower bar, possible valley

Step 11: i=10 height 2 > top height[9]=1, pop 9 Calc: dist=10-8-1=1, bh=min(2,2)-1=1, water+=1 (total=6) 2 == height[8]=2 (not >), push 10

Stack: [7,8,10]
Total water: 6

Why: Found right boundary (10), trapped 1 unit over bar 9 (between 8 and 10)

Step 12: i=11 height 1 < top height[10]=2, push 11

Stack: [7,8,10,11]
Total water: 6

Why: Lower bar, possible valley (end of array)

Result:

Total water trapped = 6 units
Final stack state: [7,8,10,11]

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class TrappingRainWater {
    public static int Trap(int[] height) {
        int totalWater = 0;
        Stack<int> stack = new Stack<int>();
        for (int i = 0; i < height.Length; i++) {
            while (stack.Count > 0 && height[i] > height[stack.Peek()]) {
                int top = stack.Pop();
                if (stack.Count == 0) break;
                int distance = i - stack.Peek() - 1;
                int boundedHeight = Math.Min(height[i], height[stack.Peek()]) - height[top];
                totalWater += distance * boundedHeight;
            }
            stack.Push(i);
        }
        return totalWater;
    }

    static void Main() {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        int trapped = Trap(height);
        Console.WriteLine(trapped);
    }
}

while (stack.Count > 0 && height[i] > height[stack.Peek()]) {

Check if current bar is taller than top of stack to find right boundary

int top = stack.Pop();

Pop the top bar which is the bottom of a potential water container

if (stack.Count == 0) break;

No left boundary to trap water if stack empty after pop

int distance = i - stack.Peek() - 1;

Calculate horizontal distance between left and right boundaries

int boundedHeight = Math.Min(height[i], height[stack.Peek()]) - height[top];

Calculate height of trapped water bounded by shorter boundary

totalWater += distance * boundedHeight;

Add trapped water volume for this segment

stack.Push(i);

Push current bar index as new potential boundary

Output

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 much faster

Edge Cases

Empty height array

Returns 0 as no bars to trap water

DSA C#

for (int i = 0; i < height.Length; i++) {

All bars same height

No water trapped, returns 0

DSA C#

while (stack.Count > 0 && height[i] > height[stack.Peek()]) {

Strictly increasing or decreasing bars

No trapped water, returns 0

DSA C#

while (stack.Count > 0 && height[i] > height[stack.Peek()]) {

When to Use This Pattern

When you see a problem asking how much water is trapped between bars or heights, use the stack pattern to efficiently find boundaries and calculate trapped water.

Common Mistakes

Mistake: Not checking if stack is empty before accessing stack.Peek() after popping
Fix: Add a check to break the loop if stack becomes empty after popping

Mistake: Calculating distance or bounded height incorrectly by mixing indices or heights
Fix: Use i - stack.Peek() - 1 for distance and min of heights at i and stack.Peek() minus height at popped index for bounded height

Summary

Calculates how much rain water is trapped between bars using a stack to find boundaries.

Use when you need to find trapped water efficiently in a height array.

The stack helps find left and right boundaries quickly to measure trapped water volume.

Practice

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

easy

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

B. To store the total amount of trapped water

C. To sort the height array in ascending order

D. To reverse the height array for easier calculation

Solution

1. Step 1: Understand the role of the stack

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

2. Step 2: Explain why other options are incorrect

   The stack does not store water amount, sort, or reverse the array; it helps find boundaries.

3. Final Answer:

   To keep track of bars that are not yet processed for water trapping -> Option A

4. Quick Check:

   Stack tracks bars for trapping water = A [OK]

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

Common Mistakes:

• Thinking stack stores water amount directly
• Assuming stack sorts or reverses the array
• Confusing stack with a queue

2. Which of the following C# code snippets correctly declares a stack to be used for trapping rain water heights?

easy

A. List<int> stack = new List<int>();

B. Stack<int> stack = new Stack<int>();

C. Stack stack = new Stack();

D. Queue<int> stack = new Queue<int>();

Solution

1. Step 1: Identify correct stack declaration

   Stack<int> stack = new Stack<int>(); uses generic Stack<int> which is type-safe and correct for storing indices.

2. Step 2: Explain why others are incorrect

   Stack stack = new Stack(); is non-generic and less type-safe; C uses List, not stack; D uses Queue, wrong data structure.

3. Final Answer:

   Stack<int> stack = new Stack<int>(); -> Option B

4. Quick Check:

   Generic Stack<int> is correct stack declaration [OK]

Hint: Use generic Stack<int> for indices in C# [OK]

Common Mistakes:

• Using non-generic Stack without type safety
• Using List instead of Stack
• Confusing Queue with Stack

3. What is the output of the following C# code snippet that uses stack to calculate trapped rain water?

int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
int water = 0;
Stack<int> stack = new Stack<int>();
for (int i = 0; i < height.Length; i++) {
    while (stack.Count > 0 && height[i] > height[stack.Peek()]) {
        int top = stack.Pop();
        if (stack.Count == 0) break;
        int distance = i - stack.Peek() - 1;
        int boundedHeight = Math.Min(height[i], height[stack.Peek()]) - height[top];
        water += distance * boundedHeight;
    }
    stack.Push(i);
}
Console.WriteLine(water);

medium

A. 5

B. 8

C. 7

D. 6

Solution

1. Step 1: Trace the stack operations and water calculation

   The code calculates trapped water for the given height array using stack logic. The total trapped water is 6 units.

2. Step 2: Confirm calculation matches known example

   This is a classic example where trapped water is known to be 6 units for the given heights.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Trapped water for given heights = 6 [OK]

Hint: Classic example traps 6 units water [OK]

Common Mistakes:

• Miscounting distance or bounded height
• Forgetting to check stack empty before popping
• Mixing up indices and heights

4. Identify the bug in the following C# code snippet for trapping rain water using stack:

int[] height = {4,2,0,3,2,5};
int water = 0;
Stack<int> stack = new Stack<int>();
for (int i = 0; i < height.Length; i++) {
    while (stack.Count > 0 && height[i] >= height[stack.Peek()]) {
        int top = stack.Pop();
        if (stack.Count == 0) break;
        int distance = i - stack.Peek() - 1;
        int boundedHeight = Math.Min(height[i], height[stack.Peek()]) - height[top];
        water += distance * boundedHeight;
    }
    stack.Push(i);
}
Console.WriteLine(water);

medium

A. The distance calculation is incorrect

B. The stack should be a Queue instead

C. The comparison should be > instead of >= in the while condition

D. The boundedHeight calculation should use Max instead of Min

Solution

1. Step 1: Analyze the while loop condition

   The condition uses >= which causes incorrect popping when heights are equal, leading to wrong water calculation.

2. Step 2: Correct condition and explain impact

   Changing >= to > fixes the logic by only popping when current height is strictly greater, preserving correct boundaries.

3. Final Answer:

   The comparison should be > instead of >= in the while condition -> Option C

4. Quick Check:

   Use > not >= in while condition [OK]

Hint: Use > not >= to avoid wrong pops [OK]

Common Mistakes:

• Using >= causes extra pops and wrong water
• Confusing stack with queue
• Incorrect distance or boundedHeight formulas

5. Given the height array int[] height = {5,2,1,2,1,5};, what is the total trapped rain water calculated using the stack-based algorithm?

hard

A. 12

B. 10

C. 8

D. 14

Solution

1. Step 1: Visualize trapped water between bars

   Between the two 5-height bars at ends, water is trapped over lower bars: (5-2)+(5-1)+(5-2)+(5-1) = 3+4+3+4 but we must count carefully by positions.

2. Step 2: Calculate trapped water using stack logic

   Trapped water units are 3 (between 5 and 2), 1 (between 2 and 1), 3 (between 2 and 1), and 5 (between 1 and 5), total 12 units.

3. Final Answer:

   12 -> Option A

4. Quick Check:

   Trapped water total = 12 units [OK]

Hint: Sum water trapped between highest bars [OK]

Common Mistakes:

• Adding heights instead of differences
• Ignoring boundaries at array ends
• Miscounting trapped water units