Trapping Rain Water Problem in DSA C# - Build from Scratch

Trapping Rain Water Problem

📖 Scenario: Imagine you have a row of walls of different heights. When it rains, water gets trapped between these walls. We want to find out how much water is trapped after the rain.

🎯 Goal: Build a program that calculates the total amount of trapped rain water between walls represented by an array of heights.

📋 What You'll Learn

Create an integer array called heights with exact values representing wall heights.

Create two integer arrays called leftMax and rightMax to store the maximum wall height from the left and right sides respectively.

Calculate the trapped water using the heights, leftMax, and rightMax arrays.

Print the total trapped water as an integer.

💡 Why This Matters

🌍 Real World

This problem models how water collects in valleys between walls or buildings, useful in civil engineering and urban planning.

💼 Career

Understanding this problem helps in algorithm design, problem-solving skills, and is commonly asked in software engineering interviews.

1

Create the wall heights array

Create an integer array called heights with these exact values: 0,1,0,2,1,0,1,3,2,1,2,1.

DSA C#

// Create the heights array with the given values
// Your code here

Hint

Use int[] heights = { ... }; to create the array with the exact values.

2

Create leftMax and rightMax arrays

Create two integer arrays called leftMax and rightMax with the same length as heights. Initialize them with zeros.

DSA C#

int[] heights = {0,1,0,2,1,0,1,3,2,1,2,1};
// Create leftMax and rightMax arrays with the same length as heights
// Your code here

Hint

Use new int[heights.Length] to create arrays of the same size filled with zeros.

3

Calculate leftMax, rightMax and trapped water

Fill leftMax by iterating from left to right, storing the maximum height so far. Fill rightMax by iterating from right to left, storing the maximum height so far. Then calculate total trapped water by summing the minimum of leftMax[i] and rightMax[i] minus heights[i] for each index i. Store the total in an integer variable called totalWater.

DSA C#

int[] heights = {0,1,0,2,1,0,1,3,2,1,2,1};
int[] leftMax = new int[heights.Length];
int[] rightMax = new int[heights.Length];
// Calculate leftMax array
// Calculate rightMax array
// Calculate total trapped water in totalWater
// Your code here

Hint

Use two loops to fill leftMax and rightMax. Then use a loop to sum trapped water into totalWater.

4

Print the total trapped water

Print the value of totalWater using Console.WriteLine.

DSA C#

int[] heights = {0,1,0,2,1,0,1,3,2,1,2,1};
int[] leftMax = new int[heights.Length];
int[] rightMax = new int[heights.Length];

leftMax[0] = heights[0];
for (int i = 1; i = 0; i--)
{
    rightMax[i] = Math.Max(rightMax[i + 1], heights[i]);
}

int totalWater = 0;
for (int i = 0; i < heights.Length; i++)
{
    totalWater += Math.Min(leftMax[i], rightMax[i]) - heights[i];
}
// Print totalWater
// Your code here

Hint

Use Console.WriteLine(totalWater); to print the result.

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