Trapping Rain Water Problem in DSA C#

Mental Model

Imagine bars of different heights and rainwater trapped between them. The water above each bar depends on the tallest bars to its left and right.

Analogy: Think of a row of buildings with different heights after rain. Water collects in the dips between taller buildings, like puddles trapped between walls.

Height bars: 3 0 2 0 4
Visual:
 4 |       ↑
 3 | ↑     | 
 2 | |   ↑ | 
 1 | |   | | 
 0 |_|___|_|_

Dry Run Walkthrough

Input: heights: [3, 0, 2, 0, 4]

Goal: Calculate total trapped rainwater between bars

Step 1: Find max height to the left of each bar

leftMax: [3, 3, 3, 3, 4]

Why: We need left boundaries to know how much water can be trapped

Step 2: Find max height to the right of each bar

rightMax: [4, 4, 4, 4, 4]

Why: We need right boundaries to know how much water can be trapped

Step 3: Calculate trapped water at each bar: min(leftMax, rightMax) - height

water: [0, 3, 1, 3, 0]

Why: Water trapped depends on the smaller boundary minus current height

Step 4: Sum all trapped water amounts

total water = 0 + 3 + 1 + 3 + 0 = 7

Why: Total trapped water is sum of water above each bar

Result:

Final trapped water: 7 units

Annotated Code

DSA C#

using System;

class TrappingRainWater {
    public static int Trap(int[] height) {
        int n = height.Length;
        if (n == 0) return 0;

        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]);
        }

        int trappedWater = 0;
        for (int i = 0; i < n; i++) {
            trappedWater += Math.Min(leftMax[i], rightMax[i]) - height[i];
        }

        return trappedWater;
    }

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

leftMax[0] = height[0];

initialize left max with first bar height

for (int i = 1; i < n; i++) { leftMax[i] = Math.Max(leftMax[i - 1], height[i]); }

build left max array by tracking highest bar from left

rightMax[n - 1] = height[n - 1];

initialize right max with last bar height

for (int i = n - 2; i >= 0; i--) { rightMax[i] = Math.Max(rightMax[i + 1], height[i]); }

build right max array by tracking highest bar from right

for (int i = 0; i < n; i++) { trappedWater += Math.Min(leftMax[i], rightMax[i]) - height[i]; }

calculate trapped water at each bar and accumulate total

Output

7

Complexity Analysis

Time: O(n) because we traverse the height array a few times linearly

Space: O(n) because we use two extra arrays to store left and right max heights

vs Alternative: Compared to brute force O(n^2) checking left and right max for each bar, this approach is much faster using precomputed arrays

Edge Cases

empty array

returns 0 as no bars means no trapped water

DSA C#

if (n == 0) return 0;

all bars same height

returns 0 because no dips to trap water

DSA C#

calculation of trapped water results in zero for each bar

strictly increasing or decreasing bars

returns 0 because water cannot be trapped without dips

DSA C#

Math.Min(leftMax[i], rightMax[i]) - height[i] results in zero for each bar

When to Use This Pattern

When you see a problem asking how much water can be trapped between bars or heights, use the trapping rain water pattern with left and right max arrays to efficiently find trapped water.

Common Mistakes

Mistake: Calculating trapped water using only one side's max height
Fix: Use both left max and right max arrays to find the minimum boundary for each bar

Mistake: Not handling empty input array
Fix: Add a guard clause to return 0 if input array length is zero

Summary

Calculates how much rainwater can be trapped between bars of different heights.

Use when you need to find trapped water volume efficiently in a height array.

The trapped water at each bar depends on the smaller of the tallest bars to its left and right.

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