Trapping Rain Water Problem 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 for the given height array?

DSA C#

int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
int trappedWater = 0;
int left = 0, right = height.Length - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
    if (height[left] < height[right]) {
        if (height[left] >= leftMax) leftMax = height[left];
        else trappedWater += leftMax - height[left];
        left++;
    } else {
        if (height[right] >= rightMax) rightMax = height[right];
        else trappedWater += rightMax - height[right];
        right--;
    }
}
System.Console.WriteLine(trappedWater);

A 7

B 5

C 8

D 6

💡 Hint

Think about how water is trapped between the bars by comparing left and right pointers.

The code uses two pointers and keeps track of the maximum heights from left and right. It adds trapped water where the current height is less than the max height seen so far. For the given array, the total trapped water is 6 units.

🧠 Conceptual

intermediate

Understanding the Two-Pointer Approach

In the two-pointer approach to the Trapping Rain Water problem, why do we move the pointer with the smaller height inward?

A Because the larger height pointer always traps water, so it should stay fixed.

B Because the trapped water depends on the smaller boundary, so moving the smaller height pointer helps find trapped water correctly.

C Because moving the smaller pointer reduces the total trapped water.

D Because the algorithm requires moving pointers alternately regardless of height.

💡 Hint

Consider which side limits the water level at each step.

Water trapped depends on the smaller boundary between left and right. Moving the pointer with smaller height helps find trapped water correctly by updating max heights and calculating trapped water.

🔧 Debug

advanced

Identify the Error in Trapping Rain Water Code

What error will the following C# code produce when executed?

DSA C#

int[] height = {4,2,0,3,2,5};
int trappedWater = 0;
int left = 0, right = height.Length - 1;
int leftMax = 0, rightMax = 0;
while (left <= right) {
    if (height[left] < height[right]) {
        if (height[left] > leftMax) leftMax = height[left];
        else trappedWater += leftMax - height[left];
        left++;
    } else {
        if (height[right] > rightMax) rightMax = height[right];
        else trappedWater += rightMax - height[right];
        right--;
    }
}
System.Console.WriteLine(trappedWater);

A Infinite loop occurs

B The code runs and outputs 10

C The code runs and outputs 9

D IndexOutOfRangeException occurs

💡 Hint

Check the loop condition and pointer updates carefully.

The loop condition uses <= which causes left and right pointers to cross and the loop never ends because pointers are updated only inside conditions that may not always move them correctly.

❓ Predict Output

advanced

Output of Prefix and Suffix Max Arrays

What is the output of the following C# code that computes prefix and suffix max arrays for trapping rain water?

DSA C#

int[] height = {3,0,2,0,4};
int n = height.Length;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
    leftMax[i] = Math.Max(leftMax[i - 1], height[i]);
}
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
    rightMax[i] = Math.Max(rightMax[i + 1], height[i]);
}
System.Console.WriteLine(string.Join(",", leftMax));
System.Console.WriteLine(string.Join(",", rightMax));

A

3,3,2,2,4
4,4,4,4,4

B

3,3,3,3,4
4,4,4,0,4

C

3,3,3,3,4
4,4,4,4,4

D

3,0,2,0,4
4,4,4,4,4

💡 Hint

Prefix max array stores max from left to current index, suffix max from right to current index.

leftMax array stores max height from left up to each index: [3,3,3,3,4]. rightMax stores max height from right up to each index: [4,4,4,4,4].

🚀 Application

expert

Calculate Total Trapped Water for Custom Input

Given the height array {5,2,1,2,1,5}, what is the total amount of trapped rain water calculated by the standard trapping rain water algorithm?

A 12

B 10

C 8

D 14

💡 Hint

Visualize the bars and calculate trapped water between the boundaries.

The trapped water units are 3 between 5 and 2, 1 between 2 and 1, 2 between 1 and 2, 1 between 2 and 1, and 5 between 1 and 5, totaling 12 units.

Practice

1. What does the Trapping Rain Water problem ask you to find given an array of heights?

easy

A. The minimum height of the bars.

B. The maximum height of the bars.

C. The number of bars in the array.

D. The total amount of water that can be trapped between the bars.

Solution

1. Step 1: Understand the problem context

   The problem gives an array representing heights of bars and asks how much water can be trapped after raining.

2. Step 2: Identify the goal

   The goal is to calculate the total trapped water volume between bars, not just heights or counts.

3. Final Answer:

   The total amount of water that can be trapped between the bars. -> Option D

4. Quick Check:

   Trapping Rain Water = Total trapped water [OK]

Hint: Focus on trapped water volume, not bar heights or counts [OK]

Common Mistakes:

• Confusing trapped water with maximum bar height
• Counting bars instead of calculating water volume
• Ignoring the space between bars

2. Which of the following C# code snippets correctly initializes an array of heights for the Trapping Rain Water problem?

easy

A. int[] heights = new int[] {4, 2, 0, 3, 2, 5};

B. int heights = {4, 2, 0, 3, 2, 5};

C. int[] heights = (4, 2, 0, 3, 2, 5);

D. int heights[] = new int[6] {4, 2, 0, 3, 2, 5};

Solution

1. Step 1: Check array initialization syntax in C#

   Correct syntax uses int[] variable = new int[] {values};

2. Step 2: Validate each option

   int[] heights = new int[] {4, 2, 0, 3, 2, 5}; uses correct syntax; B and C have invalid syntax; D has incorrect array declaration style.

3. Final Answer:

   int[] heights = new int[] {4, 2, 0, 3, 2, 5}; -> Option A

4. Quick Check:

   C# array init = new int[] {values} [OK]

Hint: Use 'int[] arr = new int[] {values};' for array initialization [OK]

Common Mistakes:

• Missing 'new int[]' keyword
• Using parentheses instead of braces
• Incorrect array declaration syntax

3. What is the output of the following C# code snippet?

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

int Trap(int[] height) {
    int left = 0, right = height.Length - 1;
    int leftMax = 0, rightMax = 0;
    int water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) leftMax = height[left];
            else water += leftMax - height[left];
            left++;
        } else {
            if (height[right] >= rightMax) rightMax = height[right];
            else water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

medium

A. 7

B. 6

C. 5

D. 8

Solution

1. Step 1: Understand two-pointer approach in code

   Left and right pointers move inward, tracking max heights and accumulating trapped water.

2. Step 2: Trace the code with given input

   For input {0,1,0,2,1,0,1,3,2,1,2,1}, trapped water calculated is 6 units.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Two-pointer trap water = 6 [OK]

Hint: Use two-pointer method to sum trapped water efficiently [OK]

Common Mistakes:

• Miscounting trapped water units
• Confusing leftMax and rightMax updates
• Incorrect pointer movement logic

4. Identify the bug in the following C# code for the Trapping Rain Water problem:

int Trap(int[] height) {
    int left = 0, right = height.Length - 1;
    int leftMax = 0, rightMax = 0;
    int water = 0;
    while (left <= right) {
        if (height[left] < height[right]) {
            if (height[left] > leftMax) leftMax = height[left];
            else water += leftMax - height[left];
            left++;
        } else {
            if (height[right] > rightMax) rightMax = height[right];
            else water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

medium

A. The loop condition should be 'left < right' instead of 'left <= right'.

B. The comparison operators for updating leftMax and rightMax should be '>=' instead of '>'.

C. The water accumulation should be outside the if-else blocks.

D. The initial values of leftMax and rightMax should be -1.

Solution

1. Step 1: Analyze loop condition impact

   Using 'left <= right' causes double counting when left equals right, leading to incorrect water calculation.

2. Step 2: Correct loop condition

   Changing to 'left < right' prevents overlap and fixes the bug.

3. Final Answer:

   The loop condition should be 'left < right' instead of 'left <= right'. -> Option A

4. Quick Check:

   Loop condition 'left < right' avoids double counting [OK]

Hint: Use strict less-than in loop to avoid double counting [OK]

Common Mistakes:

• Using <= causes overlap and wrong water sum
• Changing comparison operators unnecessarily
• Moving water calculation outside conditions

5. Given the height array {5, 2, 1, 2, 1, 5}, what is the total trapped rain water? Explain why the trapped water forms in this case.

hard

A. 10

B. 8

C. 14

D. 12

Solution

1. Step 1: Calculate trapped water at each position

   Left max array: [5,5,5,5,5,5], Right max array: [5,5,5,5,5,5]. Water trapped = min(leftMax, rightMax) - height at each index: positions 1=3, 2=4, 3=3, 4=4.

2. Step 2: Sum trapped water and explain formation

   Total trapped water = 3+4+3+4 = 14 units. Water forms because tall bars at ends trap water over lower bars inside.

3. Final Answer:

   14 -> Option C

4. Quick Check:

   Sum trapped water = 14 units [OK]

Hint: Use leftMax and rightMax arrays to find trapped water [OK]

Common Mistakes:

• Ignoring max heights on both sides
• Calculating trapped water incorrectly per position
• Forgetting to sum all trapped units