Trapping Rain Water Using Stack in DSA C# - Execution Trace

Concept Flow - Trapping Rain Water Using Stack

Start with empty stack

↓

Iterate over each bar i

↓

While stack not empty and height[i

↓

Pop top as bottom

↓

Calculate distance and bounded height

↓

Add trapped water

↓

Push current index i to stack

↓

Repeat for all bars

↓

Return total trapped water

We scan bars left to right, using a stack to find boundaries that trap water. When current bar is taller than stack top, we pop and calculate trapped water between boundaries.

Execution Sample

DSA C#

int Trap(int[] height) {
  int water = 0, current = 0;
  Stack<int> stack = new Stack<int>();
  while (current < height.Length) {
    while (stack.Count > 0 && height[current] > height[stack.Peek()]) {
      int top = stack.Pop();
      if (stack.Count == 0) break;
      int distance = current - stack.Peek() - 1;
      int bounded_height = Math.Min(height[current], height[stack.Peek()]) - height[top];
      if (bounded_height > 0) {
        water += distance * bounded_height;
      }
    }
    stack.Push(current++);
  }
  return water;
}

Calculates trapped rain water by scanning bars and using a stack to find boundaries and trapped water between them.

Execution Table

Step	Operation	Current Index	Stack Content (indices)	Water Added	Visual State (heights)
1	Start	-	[]	0	[0,1,0,2,1,0,1,3,2,1,2,1]
2	Push current index	0	[0]	0	[0,1,0,2,1,0,1,3,2,1,2,1]
3	Push current index	1	[0,1]	0	[0,1,0,2,1,0,1,3,2,1,2,1]
4	Push current index	2	[0,1,2]	0	[0,1,0,2,1,0,1,3,2,1,2,1]
5	Pop top (2) since height[2]=0 < height[3]=2	3	[0,1]	0	[0,1,0,2,1,0,1,3,2,1,2,1]
6	Calculate trapped water: distance=3-1-1=1, bounded_height=min(2,1)-0=1	3	[0,1]	1	[0,1,0,2,1,0,1,3,2,1,2,1]
7	Add water: 1	3	[0,1]	1	[0,1,0,2,1,0,1,3,2,1,2,1]
8	Pop top (1) since height[1]=1 < height[3]=2	3	[0]	1	[0,1,0,2,1,0,1,3,2,1,2,1]
9	Calculate trapped water: distance=3-0-1=2, bounded_height=min(2,0)-1=-1 (ignore)	3	[0]	1	[0,1,0,2,1,0,1,3,2,1,2,1]
10	Push current index	3	[0,3]	1	[0,1,0,2,1,0,1,3,2,1,2,1]
11	Push current index	4	[0,3,4]	1	[0,1,0,2,1,0,1,3,2,1,2,1]
12	Push current index	5	[0,3,4,5]	1	[0,1,0,2,1,0,1,3,2,1,2,1]
13	Pop top (5) since height[5]=0 < height[6]=1	6	[0,3,4]	1	[0,1,0,2,1,0,1,3,2,1,2,1]
14	Calculate trapped water: distance=6-4-1=1, bounded_height=min(1,1)-0=1	6	[0,3,4]	2	[0,1,0,2,1,0,1,3,2,1,2,1]
15	Add water: total=2	6	[0,3,4]	2	[0,1,0,2,1,0,1,3,2,1,2,1]
16	Push current index	6	[0,3,4,6]	2	[0,1,0,2,1,0,1,3,2,1,2,1]
17	Pop top (6) since height[6]=1 < height[7]=3	7	[0,3,4]	2	[0,1,0,2,1,0,1,3,2,1,2,1]
18	Calculate trapped water: distance=7-4-1=2, bounded_height=min(3,1)-1=0	7	[0,3,4]	2	[0,1,0,2,1,0,1,3,2,1,2,1]
19	Pop top (4) since height[4]=1 < height[7]=3	7	[0,3]	2	[0,1,0,2,1,0,1,3,2,1,2,1]
20	Calculate trapped water: distance=7-0-1=6, bounded_height=min(3,0)-1=-1 (ignore)	7	[0,3]	2	[0,1,0,2,1,0,1,3,2,1,2,1]
21	Push current index	7	[0,3,7]	2	[0,1,0,2,1,0,1,3,2,1,2,1]
22	Push current index	8	[0,3,7,8]	2	[0,1,0,2,1,0,1,3,2,1,2,1]
23	Push current index	9	[0,3,7,8,9]	2	[0,1,0,2,1,0,1,3,2,1,2,1]
24	Pop top (9) since height[9]=1 < height[10]=2	10	[0,3,7,8]	2	[0,1,0,2,1,0,1,3,2,1,2,1]
25	Calculate trapped water: distance=10-8-1=1, bounded_height=min(2,2)-1=1	10	[0,3,7,8]	3	[0,1,0,2,1,0,1,3,2,1,2,1]
26	Add water: total=3	10	[0,3,7,8]	3	[0,1,0,2,1,0,1,3,2,1,2,1]
27	Push current index	10	[0,3,7,8,10]	3	[0,1,0,2,1,0,1,3,2,1,2,1]
28	Push current index	11	[0,3,7,8,10,11]	3	[0,1,0,2,1,0,1,3,2,1,2,1]
29	End of array reached	-	[0,3,7,8,10,11]	3	[0,1,0,2,1,0,1,3,2,1,2,1]

💡 Reached end of array, total trapped water = 6 units

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 11	After Step 16	After Step 21	After Step 24	Final
current	0	1	3	6	7	10	11	12
stack	[]	[0]	[0,1,2]	[0,3,4,6]	[0,3,7]	[0,3,7,8]	[0,3,7,8,10,11]	[0,3,7,8,10,11]
water	0	0	1	2	2	2	3	6

Key Moments - 3 Insights

Why do we pop from the stack only when current bar is taller than the top of the stack?

Because popping happens only when we find a right boundary taller than the bottom bar (stack top). This lets us calculate trapped water between left and right boundaries. See execution_table rows 5-8 where popping starts when height[current] > height[stack.top].

Why do we check if the stack is empty after popping before calculating water?

If the stack is empty after popping, it means no left boundary exists to trap water, so we cannot calculate trapped water. This is shown in execution_table row 9 where calculation is skipped if stack is empty.

How is the trapped water amount calculated?

Trapped water = distance between boundaries * bounded height. Distance is current index minus new stack top minus one. Bounded height is min of left and right boundary heights minus bottom height. See execution_table rows 6 and 14 for examples.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the trapped water added?

A 2

B 0

C 1

D 3

💡 Hint

Check the 'Water Added' column at step 6 in execution_table.

At which step does the total trapped water first increase to 2 units?

A Step 14

B Step 7

C Step 16

D Step 26

💡 Hint

Look at the 'Water Added' column and total water accumulation in execution_table rows.

If the height at index 5 was increased from 0 to 2, how would the trapped water change at step 14?

A It would increase

B It would decrease

C It would stay the same

D No water would be trapped

💡 Hint

Consider how bounded height is calculated using min heights and bottom height at step 14.

Concept Snapshot

Trapping Rain Water Using Stack:
- Use a stack to store indices of bars
- Iterate bars left to right
- While current bar taller than stack top:
  - Pop top as bottom
  - Calculate distance and bounded height
  - Add trapped water = distance * bounded height
- Push current index
- Return total trapped water

Full Transcript

This visualization shows how to calculate trapped rain water using a stack. We scan the array of bar heights from left to right. We keep indices in a stack representing bars that may form boundaries. When the current bar is taller than the bar at the top of the stack, we pop the top as the bottom of a container. We then calculate the distance between the current bar and the new top of the stack, and the bounded height as the minimum of the two boundary bars minus the bottom bar height. Multiplying distance and bounded height gives trapped water for that segment, which we add to the total. We continue this process until all bars are processed. The execution table shows each step, stack content, water added, and the visual state of the heights. Variable tracker shows how current index, stack, and water change over time. Key moments clarify why popping happens only when current bar is taller, why we check for empty stack, and how trapped water is calculated. The quiz tests understanding of trapped water calculation and stack operations. This method efficiently computes trapped water in one pass using a stack.

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