Trapping Rain Water Using Stack in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trapping Rain Water Calculation

What is the output of the following C# code that calculates trapped rain water using a stack?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static 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];
                water += distance * bounded_height;
            }
            stack.Push(current);
            current++;
        }
        return water;
    }

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

A 6

B 5

C 7

D 8

💡 Hint

Think about how the stack helps find boundaries to trap water between bars.

The code uses a stack to find the left and right boundaries for trapped water. It calculates trapped water by measuring the distance between boundaries and the height difference. For the given input, the total trapped water is 6 units.

🧠 Conceptual

intermediate

Understanding Stack Usage in Trapping Rain Water

Why does the stack-based approach use a stack to solve the trapping rain water problem?

A To reverse the array of heights for easier calculation

B To store the heights of bars in sorted order for quick access

C To keep track of indices of bars that are not yet processed and find boundaries for trapped water

D To count the total number of bars in the elevation map

💡 Hint

Think about how the stack helps identify left and right boundaries for water trapping.

The stack stores indices of bars that form boundaries. When a higher bar is found, it means water can be trapped between the current bar and the bar at the stack's top. This helps calculate trapped water efficiently.

🔧 Debug

advanced

Identify the Error in Trapping Rain Water Code

What error will the following code produce when run?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static 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];
                water += distance * bounded_height;
            }
            stack.Push(current);
            current++;
        }
        return water;
    }

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

A Outputs 7 due to incorrect comparison operator

B No error, outputs 6

C Throws InvalidOperationException due to popping from empty stack

D Outputs 0 because water calculation is skipped

💡 Hint

Check the comparison operator in the inner while loop condition.

Using '>=' instead of '>' causes the algorithm to incorrectly calculate trapped water, resulting in an output of 7 instead of 6.

📝 Syntax

advanced

Syntax Error in Stack-Based Trapping Rain Water Code

Which option contains a syntax error in the C# code for trapping rain water using a stack?

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];
            water += distance * bounded_height;
        }
        stack.Push(current);
        current++;
    }
    return water;
}

A Missing return statement

B Missing semicolon after int top = stack.Pop()

C Using 'break' outside of loop

D Incorrect method name stack.Peek instead of stack.peek

💡 Hint

Look carefully at the line where a value is popped from the stack.

In C#, each statement must end with a semicolon. The line 'int top = stack.Pop()' is missing a semicolon, causing a syntax error.

🚀 Application

expert

Maximum Water Trapped for Large Input

Given the input array representing heights: [5,2,1,2,1,5], what is the total amount of trapped rain water calculated by the stack-based algorithm?

A 12

B 15

C 13

D 14

💡 Hint

Visualize the bars and calculate trapped water between boundaries.

The trapped water is calculated between the bars at indices 0 and 5 with dips in between. The total trapped water is 14 units.

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