Trapping Rain Water Problem in DSA Java - Execution Trace

Concept Flow - Trapping Rain Water Problem

Start with height array

↓

Initialize left, right pointers

↓

While left < right

↓

Compare height[left

↓

If height[left

↓

Update left max

↓

Calculate trapped water at left

↓

Move left pointer right

↓

Repeat until left >= right

↓

Return total trapped water

The algorithm uses two pointers from both ends, updating max heights and calculating trapped water step-by-step until pointers meet.

Execution Sample

DSA Java

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

Calculates trapped water by moving two pointers inward, updating max heights and accumulating trapped water.

Execution Table

Step	Operation	Left Pointer	Right Pointer	Left Max	Right Max	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	0	0	[0,1,0,2,1,0,1,3,2,1,2,1]
3	height[left]=0 >= leftMax=0? Yes, 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 right	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? No	1	11	0	0	0	0	[0,1,0,2,1,0,1,3,2,1,2,1]
6	height[right]=1 >= rightMax=0? Yes, 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 left	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	0	0	[0,1,0,2,1,0,1,3,2,1,2,1]
9	height[left]=1 >= leftMax=0? Yes, 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 right	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	1	1	[0,1,0,2,1,0,1,3,2,1,2,1]
12	height[left]=0 >= leftMax=1? No, add water=1-0=1	2	10	1	1	1	1	[0,1,0,2,1,0,1,3,2,1,2,1]
13	Move left pointer right	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? No	3	10	1	1	1	1	[0,1,0,2,1,0,1,3,2,1,2,1]
15	height[right]=2 >= rightMax=1? Yes, 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 left	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	0	1	[0,1,0,2,1,0,1,3,2,1,2,1]
18	height[right]=1 >= rightMax=2? No, add water=2-1=1	3	9	1	2	1	2	[0,1,0,2,1,0,1,3,2,1,2,1]
19	Move right pointer left	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? No	3	8	1	2	1	2	[0,1,0,2,1,0,1,3,2,1,2,1]
21	height[right]=2 >= rightMax=2? Yes, 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 left	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	0	2	[0,1,0,2,1,0,1,3,2,1,2,1]
24	height[left]=2 >= leftMax=1? Yes, 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 right	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	1	3	[0,1,0,2,1,0,1,3,2,1,2,1]
27	height[left]=1 >= leftMax=2? No, add water=2-1=1	4	7	2	2	1	3	[0,1,0,2,1,0,1,3,2,1,2,1]
28	Move left pointer right	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	2	5	[0,1,0,2,1,0,1,3,2,1,2,1]
30	height[left]=0 >= leftMax=2? No, add water=2-0=2	5	7	2	2	2	5	[0,1,0,2,1,0,1,3,2,1,2,1]
31	Move left pointer right	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	1	6	[0,1,0,2,1,0,1,3,2,1,2,1]
33	height[left]=1 >= leftMax=2? No, add water=2-1=1	6	7	2	2	1	6	[0,1,0,2,1,0,1,3,2,1,2,1]
34	Move left pointer right	7	7	2	2	1	6	[0,1,0,2,1,0,1,3,2,1,2,1]
35	left pointer meets right pointer, stop	7	7	2	2	0	6	[0,1,0,2,1,0,1,3,2,1,2,1]

💡 left pointer meets right pointer at index 7, loop ends

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	After 12	After 13	After 14	Final
left	0	1	2	3	4	5	6	7	7	7	7	7	7	7	7	7
right	11	10	9	8	7	7	7	7	7	7	7	7	7	7	7	7
leftMax	0	0	1	1	2	2	2	2	2	2	2	2	2	2	2	2
rightMax	0	1	1	2	2	2	2	2	2	2	2	2	2	2	2	2
water	0	0	0	1	1	2	3	5	6	6	6	6	6	6	6	6

Key Moments - 3 Insights

Why do we move the pointer with the smaller height instead of the larger one?

Because trapped water depends on the smaller boundary. Moving the smaller pointer allows us to find a taller boundary to trap water. See execution_table steps 2,5,8 where left or right pointer moves based on comparison.

Why do we update leftMax or rightMax only when current height is greater or equal?

Updating max height ensures we have the highest boundary so far to calculate trapped water correctly. If current height is less, trapped water is added as difference. See execution_table steps 3,6,9,15.

Why does the loop stop when left meets right?

Because all positions between left and right have been processed for trapped water. No more space to trap water beyond that. See execution_table step 35 where left=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 right pointer first move left from index 11 to 10?

A Step 6

B Step 7

C Step 5

D Step 8

💡 Hint

Look at 'Right Pointer' column changes in execution_table rows.

If the height at index 5 was increased from 0 to 3, how would the water trapped change at step 30?

A Water added would be 0 instead of 2

B Water added would increase to 3

C Water added would remain 2

D Water added would decrease to 1

💡 Hint

Check how water added is calculated as leftMax - height[left] at step 30 in execution_table.

Concept Snapshot

Trapping Rain Water Problem:
- Use two pointers at array ends
- Track max height left and right
- Move pointer with smaller height
- Add trapped water = maxHeight - currentHeight if lower
- Stop when pointers meet
- Return total trapped water

Full Transcript

The Trapping Rain Water problem is solved by using two pointers starting at the left and right ends of the height array. We keep track of the highest wall seen so far from the left and right sides (leftMax and rightMax). At each step, we compare the heights at the pointers. We move the pointer with the smaller height inward because trapped water depends on the smaller boundary. If the current height at that pointer is less than the max height seen so far on that side, we add the difference to the total trapped water. Otherwise, we update the max height. We repeat this until the two pointers meet. The total accumulated water is the answer. 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 the smaller pointer, why max heights update only when current height is higher, and why the loop stops when pointers meet. The visual quiz tests understanding of water addition, pointer movement, and effect of height changes.

Practice

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

easy

A. The total amount of water that can be trapped between the bars after raining

B. The maximum height of the bars in the array

C. The minimum height of the bars in the array

D. The number of bars that are taller than their neighbors

Solution

1. Step 1: Understand the problem statement

   The problem asks to calculate how much water can be trapped between bars of different heights after it rains.

2. Step 2: Identify the goal

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

3. Final Answer:

   The total amount of water that can be trapped between the bars after raining -> Option A

4. Quick Check:

   Trapping rain water = total trapped water volume [OK]

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

Common Mistakes:

• Confusing trapped water with max bar height
• Counting bars taller than neighbors instead of water
• Calculating minimum height instead of trapped water

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

easy

A. int[] heights = new int(6) {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 = {4, 2, 0, 3, 2, 5};

Solution

1. Step 1: Check Java array initialization syntax

   In Java, arrays are initialized with curly braces {} and type declaration like int[].

2. Step 2: Validate each option

   int[] heights = {4, 2, 0, 3, 2, 5}; uses correct syntax: int[] heights = {4, 2, 0, 3, 2, 5}; Options B, C, and D use invalid syntax.

3. Final Answer:

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

4. Quick Check:

   Java array init uses {} with type[] [OK]

Hint: Use curly braces {} with type[] to initialize arrays [OK]

Common Mistakes:

• Using square brackets [] without type[]
• Using parentheses () instead of braces {}
• Trying to initialize array with new int(size) and values together

3. What is the output of the following Java code snippet for trapping rain water?

int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println(trap(height));

public static 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;
}

medium

A. 5

B. 6

C. 7

D. 8

Solution

1. Step 1: Understand two-pointer approach

   We use two pointers left and right, track max heights on both sides, and add trapped water where possible.

2. Step 2: Trace the code with given input

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

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Two-pointer trap calculation = 6 [OK]

Hint: Use two pointers and track max heights from both ends [OK]

Common Mistakes:

• Not updating leftMax and rightMax correctly
• Adding negative water amounts
• Confusing left and right pointer movements

4. Identify the bug in this Java method for trapping rain water:

public static 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;
}

medium

A. The water calculation should add height[left] instead of subtracting

B. The comparison should be 'height[left] <= height[right]' instead of '<'

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

D. leftMax and rightMax should be initialized to 1 instead of 0

Solution

1. Step 1: Analyze loop condition impact

   The loop uses 'left <= right', which causes double counting when left == right.

2. Step 2: Correct loop condition

   Changing to 'left < right' prevents overlapping pointers and avoids incorrect water calculation.

3. Final Answer:

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

4. Quick Check:

   Loop condition 'left < right' avoids overlap [OK]

Hint: Use strict less than in loop to avoid pointer overlap [OK]

Common Mistakes:

• Using <= causes double counting at same index
• Changing comparison operators incorrectly
• Initializing max heights incorrectly

5. Given the height array {3, 0, 2, 0, 4}, what is the total trapped rain water? Explain how the trapped water is calculated step-by-step.

hard

A. 7

B. 6

C. 5

D. 8

Solution

1. Step 1: Calculate leftMax and rightMax arrays

   leftMax = [3, 3, 3, 3, 4], rightMax = [4, 4, 4, 4, 4]

2. Step 2: Calculate trapped water at each index

   Water trapped = min(leftMax[i], rightMax[i]) - height[i] = [0, 3, 1, 3, 0] Sum = 0 + 3 + 1 + 3 + 0 = 7

3. Step 3: Re-check calculation for correctness

   At index 1: min(3,4)-0=3 At index 2: min(3,4)-2=1 At index 3: min(3,4)-0=3 Sum = 7 units trapped water

4. Final Answer:

   7 -> Option A

5. Quick Check:

   Sum trapped water = 7 units [OK]

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

Common Mistakes:

• Forgetting to take minimum of leftMax and rightMax
• Subtracting height incorrectly
• Not summing trapped water at all indices