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

Recall & Review

beginner

What is the main goal of the Trapping Rain Water Problem?

To find how much water can be trapped between bars of different heights after raining.

beginner

In the Trapping Rain Water Problem, what does the height array represent?

Each element represents the height of a vertical bar at that position.

intermediate

What is the purpose of using two pointers in the optimized solution of the Trapping Rain Water Problem?

To scan from both ends towards the center, calculating trapped water efficiently without extra space.

intermediate

Explain why we keep track of left_max and right_max in the Trapping Rain Water Problem.

They represent the highest bars seen so far from the left and right sides, helping to calculate trapped water at each position.

intermediate

What is the time complexity of the two-pointer approach for the Trapping Rain Water Problem?

O(n), where n is the number of bars, because each bar is visited at most once.

What does the Trapping Rain Water Problem calculate?

A The tallest bar height

B The total volume of water trapped between bars

C The number of bars

D The width of the bars

The problem calculates how much water can be trapped between bars after raining.

Which data structure is commonly used to solve the Trapping Rain Water Problem efficiently?

A Two pointers

B Stack only

C Queue

D Linked list

The two-pointer approach is efficient and commonly used to solve this problem.

What do left_max and right_max represent in the solution?

A Total water trapped

B Lowest bars from left and right sides

C Highest bars from left and right sides

D Number of bars

They track the highest bars seen so far from each side to calculate trapped water.

What is the space complexity of the two-pointer approach?

A O(n^2)

B O(n)

C O(log n)

D O(1)

The two-pointer approach uses constant extra space.

If the height array is [0,1,0,2,1,0,1,3,2,1,2,1], what is the total trapped water?

A 6

B 4

C 5

D 3

The total trapped water for this input is 6 units.

Describe the two-pointer approach to solve the Trapping Rain Water Problem.

Think about scanning from both ends and comparing heights.

Explain why the trapped water at a position depends on the minimum of left_max and right_max minus the height at that position.

Imagine water filling between walls of different heights.

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