Trapping Rain Water Using Stack in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a stack to solve the Trapping Rain Water problem?

Use a stack to keep track of bars that are bounded by higher bars on both sides. When a higher bar is found, calculate trapped water with the bars in the stack.

beginner

In the stack approach, what does each element in the stack represent?

Each element represents the index of a bar in the height array, used to calculate trapped water when a taller bar is found.

intermediate

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

Because a taller bar on the right can trap water with the popped bar as the bottom and the current bar as the right boundary.

intermediate

How do you calculate the width of trapped water between bars in the stack method?

Width is the distance between the current index and the new top of the stack minus one (currentIndex - stackTop - 1).

beginner

What is the time complexity of the Trapping Rain Water problem using the stack approach?

O(n), because each bar is pushed and popped at most once from the stack.

What does the stack store in the Trapping Rain Water problem?

A Heights of bars

B Indices of bars

C Water trapped at each bar

D Width between bars

The stack stores indices of bars to calculate trapped water when a taller bar is found.

When do you calculate trapped water in the stack approach?

A When current bar is taller than top of stack

B When current bar is shorter than top of stack

C At the end of the array only

D Before pushing any bar

Trapped water is calculated when the current bar is taller than the top of the stack.

What is the role of the 'bottom' bar in the stack method?

A It stores the water amount

B It acts as the right boundary

C It acts as the left boundary

D It acts as the bottom of the trapped water

The popped bar acts as the bottom of the trapped water between two taller bars.

How is the height of trapped water calculated?

A Difference between current and previous bar heights

B Maximum of left and right bar heights minus bottom bar height

C Minimum of left and right bar heights minus bottom bar height

D Sum of left and right bar heights

Height is the minimum of left and right boundaries minus the bottom bar height.

What is the space complexity of the stack approach?

A O(n)

B O(log n)

C O(1)

D O(n^2)

The stack can hold up to n indices, so space complexity is O(n).

Explain step-by-step how the stack helps calculate trapped rain water.

Think about how water is trapped between two taller bars with a lower bar in the middle.

Describe how to calculate trapped water volume when a taller bar is found using the stack.

Focus on the geometry of trapped water between bars.

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