Trapping Rain Water Problem in DSA C# - Execution Trace

Concept Flow - Trapping Rain Water Problem

Start with height array

↓

Initialize left=0, right=end, leftMax=0, rightMax=0, water=0

↓

While left < right

↓

left height < right height?

Yes→If height[left

| No↓

If height[right

↓

Move pointers inward (left++ or right--)

↓

Repeat until left >= right

↓

Return total water trapped

The flow shows how two pointers move inward from both ends, updating max heights and accumulating trapped water step-by-step.

Execution Sample

DSA C#

int Trap(int[] height) {
  int left=0, right=height.Length-1;
  int leftMax=0, rightMax=0, 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;
}

This code calculates trapped rain water using two pointers moving inward, updating max heights and accumulating water.

Execution Table

Step	Operation	Left Pointer	Right Pointer	LeftMax	RightMax	Water Added	Total Water	Visual State
1	Initialize pointers and maxes	0	11	0	0	0	0	[0,1,0,2,1,0,1,3,2,1,2,1]
2	Compare height[left]=0 < height[right]=1	0	11	0	0	Yes	0	[0,1,0,2,1,0,1,3,2,1,2,1]
3	height[left]=0 >= leftMax=0? Update leftMax=0	0	11	0	0	0	0	[0,1,0,2,1,0,1,3,2,1,2,1]
4	Move left pointer to 1	1	11	0	0	0	0	[0,1,0,2,1,0,1,3,2,1,2,1]
5	Compare height[left]=1 < height[right]=1	1	11	0	0	No (equal)	0	[0,1,0,2,1,0,1,3,2,1,2,1]
6	height[right]=1 >= rightMax=0? Update rightMax=1	1	11	0	1	0	0	[0,1,0,2,1,0,1,3,2,1,2,1]
7	Move right pointer to 10	1	10	0	1	0	0	[0,1,0,2,1,0,1,3,2,1,2,1]
8	Compare height[left]=1 < height[right]=2	1	10	0	1	Yes	0	[0,1,0,2,1,0,1,3,2,1,2,1]
9	height[left]=1 >= leftMax=0? Update leftMax=1	1	10	1	1	0	0	[0,1,0,2,1,0,1,3,2,1,2,1]
10	Move left pointer to 2	2	10	1	1	0	0	[0,1,0,2,1,0,1,3,2,1,2,1]
11	Compare height[left]=0 < height[right]=2	2	10	1	1	Yes	0	[0,1,0,2,1,0,1,3,2,1,2,1]
12	height[left]=0 < leftMax=1? Add water=1	2	10	1	1	1	1	[0,1,0,2,1,0,1,3,2,1,2,1]
13	Move left pointer to 3	3	10	1	1	1	1	[0,1,0,2,1,0,1,3,2,1,2,1]
14	Compare height[left]=2 < height[right]=2	3	10	1	1	No (equal)	1	[0,1,0,2,1,0,1,3,2,1,2,1]
15	height[right]=2 >= rightMax=1? Update rightMax=2	3	10	1	2	0	1	[0,1,0,2,1,0,1,3,2,1,2,1]
16	Move right pointer to 9	3	9	1	2	0	1	[0,1,0,2,1,0,1,3,2,1,2,1]
17	Compare height[left]=2 < height[right]=1	3	9	1	2	No	1	[0,1,0,2,1,0,1,3,2,1,2,1]
18	height[right]=1 < rightMax=2? Add water=1	3	9	1	2	1	2	[0,1,0,2,1,0,1,3,2,1,2,1]
19	Move right pointer to 8	3	8	1	2	1	2	[0,1,0,2,1,0,1,3,2,1,2,1]
20	Compare height[left]=2 < height[right]=2	3	8	1	2	No (equal)	2	[0,1,0,2,1,0,1,3,2,1,2,1]
21	height[right]=2 >= rightMax=2? Update rightMax=2	3	8	1	2	0	2	[0,1,0,2,1,0,1,3,2,1,2,1]
22	Move right pointer to 7	3	7	1	2	0	2	[0,1,0,2,1,0,1,3,2,1,2,1]
23	Compare height[left]=2 < height[right]=3	3	7	1	2	Yes	2	[0,1,0,2,1,0,1,3,2,1,2,1]
24	height[left]=2 >= leftMax=1? Update leftMax=2	3	7	2	2	0	2	[0,1,0,2,1,0,1,3,2,1,2,1]
25	Move left pointer to 4	4	7	2	2	0	2	[0,1,0,2,1,0,1,3,2,1,2,1]
26	Compare height[left]=1 < height[right]=3	4	7	2	2	Yes	2	[0,1,0,2,1,0,1,3,2,1,2,1]
27	height[left]=1 < leftMax=2? Add water=1	4	7	2	2	1	3	[0,1,0,2,1,0,1,3,2,1,2,1]
28	Move left pointer to 5	5	7	2	2	1	3	[0,1,0,2,1,0,1,3,2,1,2,1]
29	Compare height[left]=0 < height[right]=3	5	7	2	2	Yes	3	[0,1,0,2,1,0,1,3,2,1,2,1]
30	height[left]=0 < leftMax=2? Add water=2	5	7	2	2	2	5	[0,1,0,2,1,0,1,3,2,1,2,1]
31	Move left pointer to 6	6	7	2	2	2	5	[0,1,0,2,1,0,1,3,2,1,2,1]
32	Compare height[left]=1 < height[right]=3	6	7	2	2	Yes	5	[0,1,0,2,1,0,1,3,2,1,2,1]
33	height[left]=1 < leftMax=2? Add water=1	6	7	2	2	1	6	[0,1,0,2,1,0,1,3,2,1,2,1]
34	Move left pointer to 7	7	7	2	2	1	6	[0,1,0,2,1,0,1,3,2,1,2,1]
35	Exit loop since left >= right	7	7	2	2	0	6	[0,1,0,2,1,0,1,3,2,1,2,1]

💡 left pointer (7) is no longer less than right pointer (7), loop ends

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 10	After Step 13	After Step 16	After Step 19	After Step 22	After Step 25	After Step 28	After Step 31	Final
left	0	1	1	2	3	3	3	3	4	5	6	7
right	11	11	10	10	10	9	8	7	7	7	7	7
leftMax	0	0	0	1	1	1	1	1	2	2	2	2
rightMax	0	0	1	1	1	2	2	2	2	2	2	2
water	0	0	0	0	1	1	2	2	2	3	5	6

Key Moments - 3 Insights

Why do we compare height[left] and height[right] to decide which pointer to move?

Because the trapped water depends on the smaller side's max height. The execution_table rows 2,5,8,14,17,20 show that we move the pointer at the smaller height to safely calculate trapped water.

Why do we add water as leftMax - height[left] or rightMax - height[right]?

Because water trapped at a position is limited by the smaller max height on either side minus the current height. Rows 12,18,27,30,33 show water added as difference between max height and current height.

Why does the loop stop when left >= right?

Because pointers have met or crossed, meaning all positions have been processed. Row 35 shows the exit condition when left=7 and right=7.

Visual Quiz - 3 Questions

Look at the execution_table at step 12, how much water is added and what is the total water?

A Water added=1, Total water=1

B Water added=0, Total water=0

C Water added=2, Total water=2

D Water added=1, Total water=0

💡 Hint

Check columns 'Water Added' and 'Total Water' at step 12 in execution_table

At which step does the rightMax first update to 2?

A Step 15

B Step 6

C Step 20

D Step 10

💡 Hint

Look at 'RightMax' column changes in execution_table rows around step 15

If height[left] was always greater than height[right], which pointer would move according to the flow?

A Left pointer moves

B Right pointer moves

C Both pointers move simultaneously

D Neither pointer moves

💡 Hint

Refer to concept_flow and execution_table steps where height[left] >= height[right], pointer moved is right

Concept Snapshot

Trapping Rain Water Problem:
- Use two pointers: left at start, right at end
- Track leftMax and rightMax heights
- Move pointer with smaller height inward
- Add water = maxHeight - current height if current < max
- Stop when pointers meet
- Return total trapped water

Full Transcript

The Trapping Rain Water problem is solved by using two pointers starting at both ends of the height array. We keep track of the highest wall seen from the left (leftMax) and from the right (rightMax). At each step, we compare the heights at the pointers. We move the pointer at the smaller height inward because the trapped water depends on the smaller side. If the current height is less than the max height on that side, we add the difference to the total water trapped. We update max heights when we find a taller wall. The process repeats until the pointers meet. The total water accumulated is returned. The execution table shows each step with pointer positions, max heights, water added, and the total water so far. Key moments clarify why we move pointers based on height comparison, how water is calculated, and why the loop ends when pointers meet.

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