Trapping Rain Water Problem in DSA Javascript - Execution Trace

Concept Flow - Trapping Rain Water Problem

Start with height array

↓

Calculate left max heights

↓

Calculate right max heights

↓

For each bar: min(left max, right max) - height

↓

Sum all positive differences

↓

Return total trapped water

We first find the highest wall to the left and right of each bar, then calculate trapped water by the difference between the smaller max height and current bar height.

Execution Sample

DSA Javascript

const height = [0,1,0,2,1,0,1,3,2,1,2,1];
let leftMax = [], rightMax = [];
// Calculate trapped water
let water = 0;

This code prepares arrays to store max heights from left and right, then calculates total trapped water.

Execution Table

Step	Operation	Index	leftMax	rightMax	Water Added	Total Water	Visual State
1	Initialize leftMax[0]	0	[0]	[]	0	0	Height: 0
2	Calculate leftMax[1]	1	[0,1]	[]	0	0	Height: 0,1
3	Calculate leftMax[2]	2	[0,1,1]	[]	0	0	Height: 0,1,0
4	Calculate leftMax[3]	3	[0,1,1,2]	[]	0	0	Height: 0,1,0,2
5	Calculate leftMax[4]	4	[0,1,1,2,2]	[]	0	0	Height: 0,1,0,2,1
6	Calculate leftMax[5]	5	[0,1,1,2,2,2]	[]	0	0	Height: 0,1,0,2,1,0
7	Calculate leftMax[6]	6	[0,1,1,2,2,2,2]	[]	0	0	Height: 0,1,0,2,1,0,1
8	Calculate leftMax[7]	7	[0,1,1,2,2,2,2,3]	[]	0	0	Height: 0,1,0,2,1,0,1,3
9	Calculate leftMax[8]	8	[0,1,1,2,2,2,2,3,3]	[]	0	0	Height: 0,1,0,2,1,0,1,3,2
10	Calculate leftMax[9]	9	[0,1,1,2,2,2,2,3,3,3]	[]	0	0	Height: 0,1,0,2,1,0,1,3,2,1
11	Calculate leftMax[10]	10	[0,1,1,2,2,2,2,3,3,3,3]	[]	0	0	Height: 0,1,0,2,1,0,1,3,2,1,2
12	Calculate leftMax[11]	11	[0,1,1,2,2,2,2,3,3,3,3,3]	[]	0	0	Height: 0,1,0,2,1,0,1,3,2,1,2,1
13	Initialize rightMax[last]	11	[...]	[1]	0	0	Height: ... 1
14	Calculate rightMax[10]	10	[...]	[2,1]	0	0	Height: ... 2,1
15	Calculate rightMax[9]	9	[...]	[2,2,1]	0	0	Height: ... 1,2,1
16	Calculate rightMax[8]	8	[...]	[2,2,2,1]	0	0	Height: ... 2,1,2,2
17	Calculate rightMax[7]	7	[...]	[3,2,2,2,1]	0	0	Height: ... 3,2,1,2,2
18	Calculate rightMax[6]	6	[...]	[3,3,2,2,2,1]	0	0	Height: ... 1,3,2,1,2,2
19	Calculate rightMax[5]	5	[...]	[3,3,3,2,2,2,1]	0	0	Height: ... 0,1,3,2,1,2,2
20	Calculate rightMax[4]	4	[...]	[3,3,3,3,2,2,2,1]	0	0	Height: ... 1,0,1,3,2,1,2,2
21	Calculate rightMax[3]	3	[...]	[3,3,3,3,3,2,2,2,1]	0	0	Height: ... 2,1,0,1,3,2,1,2,2
22	Calculate rightMax[2]	2	[...]	[3,3,3,3,3,3,2,2,2,1]	0	0	Height: ... 0,2,1,0,1,3,2,1,2,2
23	Calculate rightMax[1]	1	[...]	[3,3,3,3,3,3,3,2,2,2,1]	0	0	Height: ... 1,0,2,1,0,1,3,2,1,2,2
24	Calculate rightMax[0]	0	[...]	[3,3,3,3,3,3,3,3,2,2,2,1]	0	0	Height: ... 0,1,0,2,1,0,1,3,2,1,2,1
25	Calculate water at index 0	0	[...]	[...]	0	0	Water: 0
26	Calculate water at index 1	1	[...]	[...]	0	0	Water: 0
27	Calculate water at index 2	2	[...]	[...]	1	1	Water: 1
28	Calculate water at index 3	3	[...]	[...]	0	1	Water: 1
29	Calculate water at index 4	4	[...]	[...]	1	2	Water: 2
30	Calculate water at index 5	5	[...]	[...]	2	4	Water: 4
31	Calculate water at index 6	6	[...]	[...]	1	5	Water: 5
32	Calculate water at index 7	7	[...]	[...]	0	5	Water: 5
33	Calculate water at index 8	8	[...]	[...]	0	5	Water: 5
34	Calculate water at index 9	9	[...]	[...]	1	6	Water: 6
35	Calculate water at index 10	10	[...]	[...]	0	6	Water: 6
36	Calculate water at index 11	11	[...]	[...]	0	6	Water: 6
37	Return total trapped water	-	-	-	-	6	Final trapped water: 6 units
38	End	-	-	-	-	-	All bars processed

💡 All bars processed, total trapped water calculated as 6 units

Variable Tracker

Variable	Start	After Step 12	After Step 24	After Step 37
leftMax	[]	[0,1,1,2,2,2,2,3,3,3,3,3]	[0,1,1,2,2,2,2,3,3,3,3,3]	[0,1,1,2,2,2,2,3,3,3,3,3]
rightMax	[]	[]	[3,3,3,3,3,3,3,3,2,2,2,1]	[3,3,3,3,3,3,3,3,2,2,2,1]
water	0	0	0	6

Key Moments - 3 Insights

Why do we calculate leftMax and rightMax arrays before calculating trapped water?

Because trapped water at each bar depends on the tallest bar to its left and right. The execution_table rows 2-12 and 13-24 show how these arrays are built first to use in water calculation later.

Why do we take the minimum of leftMax and rightMax at each index?

Water can only be trapped up to the shorter side's height. The execution_table rows 25-36 show water added as min(leftMax, rightMax) minus current height.

Why do we add water only if the difference is positive?

If the current bar is taller or equal to min(leftMax, rightMax), no water is trapped. Execution_table rows 25-36 show water added only when positive.

Visual Quiz - 3 Questions

Look at the execution_table at step 27. How much water is trapped at index 2?

A 1

B 0

C 2

D 3

💡 Hint

Check the 'Water Added' column at step 27 in execution_table.

At which step does the total trapped water first become 4 units?

A Step 29

B Step 30

C Step 31

D Step 32

💡 Hint

Look at the 'Total Water' column in execution_table rows 29-32.

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

A Increase

B Decrease to zero

C Stay the same

D Become negative

💡 Hint

Water trapped is min(leftMax, rightMax) - height; increasing height reduces trapped water (see variable_tracker).

Concept Snapshot

Trapping Rain Water Problem:
- Use arrays leftMax and rightMax to store max heights from left and right
- For each bar, trapped water = min(leftMax[i], rightMax[i]) - height[i]
- Sum all positive trapped water values
- Result is total water trapped between bars

Full Transcript

The Trapping Rain Water problem calculates how much water can be trapped between bars of different heights. We first create two arrays: leftMax and rightMax. leftMax[i] stores the tallest bar from the start up to index i. rightMax[i] stores the tallest bar from the end up to index i. Then, for each bar, we find the smaller of leftMax[i] and rightMax[i], subtract the current bar's height, and if positive, add that to total trapped water. This process is shown step-by-step in the execution table, tracking how arrays and water totals change. Key points include why we use min of left and right max, and only add positive differences. The final total trapped water for the example is 6 units.

Practice

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

easy

A. The maximum height of the bars in the array

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

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

D. The minimum height of the bars in the array

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 between them after it rains.

2. Step 2: Identify the goal

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

3. Final Answer:

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

4. Quick Check:

   Trapping Rain Water = Total trapped water [OK]

Hint: Think of bars as walls trapping water in between [OK]

Common Mistakes:

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

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

easy

A. const heights = [4, 2, 0, 3, 2, 5];

B. let heights = (4, 2, 0, 3, 2, 5);

C. var heights = {4, 2, 0, 3, 2, 5};

D. const heights = 4, 2, 0, 3, 2, 5;

Solution

1. Step 1: Check array initialization syntax

   In JavaScript, arrays are initialized using square brackets []. const heights = [4, 2, 0, 3, 2, 5]; uses this correct syntax.

2. Step 2: Identify incorrect syntax in other options

   let heights = (4, 2, 0, 3, 2, 5); uses parentheses which is invalid for arrays. var heights = {4, 2, 0, 3, 2, 5}; uses curly braces which define objects, not arrays. const heights = 4, 2, 0, 3, 2, 5; lacks brackets and is invalid.

3. Final Answer:

   const heights = [4, 2, 0, 3, 2, 5]; -> Option A

4. Quick Check:

   Array syntax = [] [OK]

Hint: Use square brackets [] to create arrays in JavaScript [OK]

Common Mistakes:

• Using parentheses () instead of brackets [] for arrays
• Using curly braces {} which create objects, not arrays
• Missing brackets leading to syntax errors

3. What is the output of the following JavaScript code snippet that calculates trapped rain water?

function trap(height) {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let 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;
}
console.log(trap([4,2,0,3,2,5]));

medium

A. 9

B. 7

C. 8

D. 10

Solution

1. Step 1: Understand two-pointer approach

   The code uses two pointers from left and right, tracking max heights and adding trapped water where current height is less than max.

2. Step 2: Dry run with input [4,2,0,3,2,5]

   Water trapped is calculated as 2 (at index 1), 4 (at index 2), 1 (at index 3), 2 (at index 4), totaling 9 units.

3. Final Answer:

   9 -> Option A

4. Quick Check:

   Two-pointer trap water = 9 [OK]

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

Common Mistakes:

• Adding heights instead of differences
• Not updating max heights correctly
• Mixing left and right pointer logic

4. Identify the bug in this JavaScript function for trapping rain water:

function trap(height) {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let 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 pointers left and right should not be incremented or decremented inside the loop

B. The comparison operators '>' should be '>=' when updating max heights

C. The water calculation should add height[left] instead of leftMax - height[left]

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

Solution

1. Step 1: Analyze loop condition impact

   The loop uses 'left <= right' which causes the pointers to cross and may double count or cause incorrect water calculation.

2. Step 2: Correct loop condition

   Changing the condition to 'left < right' ensures pointers stop before crossing, preventing errors in trapped water calculation.

3. Final Answer:

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

4. Quick Check:

   Loop condition fix = 'left < right' [OK]

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

Common Mistakes:

• Using <= causes double counting or invalid access
• Changing comparison operators unnecessarily
• Not moving pointers causing infinite loops

5. Given the heights array [0,1,0,2,1,0,1,3,2,1,2,1], what is the total trapped rain water using the optimal two-pointer approach?

hard

A. 7

B. 5

C. 8

D. 6

Solution

1. Step 1: Apply two-pointer method on given array

   Initialize left=0, right=11, leftMax=0, rightMax=0, water=0. Move pointers inward, updating max heights and adding trapped water where current height is less than max.

2. Step 2: Calculate trapped water step-by-step

   Water trapped at positions: 1 unit at index 2, 1 at index 4, 2 at index 5, 1 at index 6, 1 at index 9; total = 6 units.

3. Final Answer:

   8 -> Option C

4. Quick Check:

   Two-pointer trap water = 8 [OK]

Hint: Track max heights from both ends and sum water differences [OK]

Common Mistakes:

• Forgetting to update max heights correctly
• Adding heights instead of differences
• Stopping pointers too early or too late