Trapping Rain Water Problem in DSA Typescript - Execution Trace

Concept Flow - Trapping Rain Water Problem

Start with height array

↓

Calculate left max for each position

↓

Calculate right max for each position

↓

For each position, find min(left max, right max)

↓

Calculate trapped water = min - height

↓

Sum all trapped water

↓

Return total trapped water

The flow shows how we find the max height to the left and right of each bar, then calculate trapped water by comparing these max heights with the current bar height.

Execution Sample

DSA Typescript

const height = [0,1,0,2,1,0,1,3,2,1,2,1];
let leftMax = new Array(height.length).fill(0);
let rightMax = new Array(height.length).fill(0);
let water = 0;
for (let i = 1; i < height.length; i++) {
  leftMax[i] = Math.max(leftMax[i-1], height[i-1]);
}

This code calculates the left max array for the height bars, which helps find trapped water on the left side.

Execution Table

Step	Operation	Index i	leftMax Array	rightMax Array	Water Added	Total Water	Visual State
1	Initialize leftMax and rightMax arrays	-	[0,0,0,0,0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	Height: 0 1 0 2 1 0 1 3 2 1 2 1
2	Calculate leftMax at i=1	1	[0,0,0,0,0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	leftMax updated at 1: 0
3	Calculate leftMax at i=2	2	[0,1,0,0,0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	leftMax updated at 2: 1
4	Calculate leftMax at i=3	3	[0,1,1,0,0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	leftMax updated at 3: 1
5	Calculate leftMax at i=4	4	[0,1,1,2,0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	leftMax updated at 4: 2
6	Calculate leftMax at i=5	5	[0,1,1,2,2,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	leftMax updated at 5: 2
7	Calculate leftMax at i=6	6	[0,1,1,2,2,2,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	leftMax updated at 6: 2
8	Calculate leftMax at i=7	7	[0,1,1,2,2,2,2,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	leftMax updated at 7: 2
9	Calculate leftMax at i=8	8	[0,1,1,2,2,2,2,3,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	leftMax updated at 8: 3
10	Calculate leftMax at i=9	9	[0,1,1,2,2,2,2,3,3,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	leftMax updated at 9: 3
11	Calculate leftMax at i=10	10	[0,1,1,2,2,2,2,3,3,3,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	leftMax updated at 10: 3
12	Calculate leftMax at i=11	11	[0,1,1,2,2,2,2,3,3,3,3,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	0	0	leftMax updated at 11: 3
13	Calculate rightMax at i=10	10	[0,1,1,2,2,2,2,3,3,3,3,0]	[1,0,0,0,0,0,0,0,0,0,0,0]	0	0	rightMax updated at 10: 1
14	Calculate rightMax at i=9	9	[0,1,1,2,2,2,2,3,3,3,3,0]	[2,2,0,0,0,0,0,0,0,0,0,0]	0	0	rightMax updated at 9: 2
15	Calculate rightMax at i=8	8	[0,1,1,2,2,2,2,3,3,3,3,0]	[2,2,2,0,0,0,0,0,0,0,0,0]	0	0	rightMax updated at 8: 2
16	Calculate rightMax at i=7	7	[0,1,1,2,2,2,2,3,3,3,3,0]	[3,3,3,3,0,0,0,0,0,0,0,0]	0	0	rightMax updated at 7: 3
17	Calculate rightMax at i=6	6	[0,1,1,2,2,2,2,3,3,3,3,0]	[3,3,3,3,3,0,0,0,0,0,0,0]	0	0	rightMax updated at 6: 3
18	Calculate rightMax at i=5	5	[0,1,1,2,2,2,2,3,3,3,3,0]	[3,3,3,3,3,3,0,0,0,0,0,0]	0	0	rightMax updated at 5: 3
19	Calculate rightMax at i=4	4	[0,1,1,2,2,2,2,3,3,3,3,0]	[3,3,3,3,3,3,3,0,0,0,0,0]	0	0	rightMax updated at 4: 3
20	Calculate rightMax at i=3	3	[0,1,1,2,2,2,2,3,3,3,3,0]	[3,3,3,3,3,3,3,3,0,0,0,0]	0	0	rightMax updated at 3: 3
21	Calculate rightMax at i=2	2	[0,1,1,2,2,2,2,3,3,3,3,0]	[3,3,3,3,3,3,3,3,3,0,0,0]	0	0	rightMax updated at 2: 3
22	Calculate rightMax at i=1	1	[0,1,1,2,2,2,2,3,3,3,3,0]	[3,3,3,3,3,3,3,3,3,3,0,0]	0	0	rightMax updated at 1: 3
23	Calculate rightMax at i=0	0	[0,1,1,2,2,2,2,3,3,3,3,0]	[3,3,3,3,3,3,3,3,3,3,3,0]	0	0	rightMax updated at 0: 3
24	Calculate trapped water at i=1	1	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,3,3,3,0]	0	0	Water at 1: min(0,3)-1=0
25	Calculate trapped water at i=2	2	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,3,3,3,0]	1	1	Water at 2: min(1,3)-0=1
26	Calculate trapped water at i=3	3	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,3,3,3,0]	0	1	Water at 3: min(2,3)-2=0
27	Calculate trapped water at i=4	4	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,3,3,3,0]	1	2	Water at 4: min(2,3)-1=1
28	Calculate trapped water at i=5	5	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,3,3,3,0]	2	4	Water at 5: min(2,3)-0=2
29	Calculate trapped water at i=6	6	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,3,3,3,0]	1	5	Water at 6: min(2,3)-1=1
30	Calculate trapped water at i=7	7	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,3,3,3,0]	0	5	Water at 7: min(3,3)-3=0
31	Calculate trapped water at i=8	8	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,3,3,3,0]	0	5	Water at 8: min(3,3)-2=0
32	Calculate trapped water at i=9	9	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,3,3,3,0]	1	6	Water at 9: min(3,3)-1=1
33	Calculate trapped water at i=10	10	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,3,3,3,0]	0	6	Water at 10: min(3,3)-2=0
34	Calculate trapped water at i=11	11	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,3,3,3,0]	0	6	Water at 11: min(3,0)-1=0
35	Return total trapped water	-	[0,1,1,2,2,2,2,3,3,3,3,3]	[3,3,3,3,3,3,3,3,3,3,3,0]	0	6	Total trapped water = 6

💡 All positions processed, total trapped water calculated as 6

Variable Tracker

Variable	Start	After Step 12	After Step 23	After Step 34	Final
leftMax	[0,0,0,0,0,0,0,0,0,0,0,0]	[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]	[0,1,1,2,2,2,2,3,3,3,3,3]
rightMax	[0,0,0,0,0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0,0,0,0,0]	[3,3,3,3,3,3,3,3,3,3,3,0]	[3,3,3,3,3,3,3,3,3,3,3,0]	[3,3,3,3,3,3,3,3,3,3,3,0]
water	0	0	0	6	6

Key Moments - 3 Insights

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

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

Why do we subtract the current height from the minimum of leftMax and rightMax?

Because water can only be trapped up to the shorter side's height minus the current bar height. Execution_table rows 24-34 show this calculation step by step.

Why is water added zero when min(leftMax, rightMax) is less than or equal to current height?

Because no water can be trapped if the current bar is taller or equal to the boundaries. This is shown in execution_table rows like 24 and 30 where water added is zero.

Visual Quiz - 3 Questions

Look at the execution_table at step 25, what is the water added at index 2?

A 1

B 0

C 2

D 3

💡 Hint

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

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

A Step 27

B Step 28

C Step 29

D Step 30

💡 Hint

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

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

A Increase

B Decrease

C Stay the same

D Become zero

💡 Hint

Consider how water trapped depends on min(leftMax, rightMax) minus height at index 5 in execution_table step 28.

Concept Snapshot

Trapping Rain Water Problem:
- Use arrays leftMax and rightMax to store max heights left and right of each bar.
- For each bar, trapped water = min(leftMax, rightMax) - height.
- Sum all trapped water values for total.
- Time complexity: O(n), Space: O(n).
- Key: water trapped depends on shorter boundary.

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 to the left of position i, and rightMax[i] stores the tallest bar to the right. Then, for each position, we find the minimum of leftMax[i] and rightMax[i], subtract the current height, and add the result to total water if positive. The execution table shows step-by-step how leftMax and rightMax arrays are built, then how water trapped at each index is calculated and summed. Key moments clarify why these arrays are needed and how the subtraction works. The visual quiz tests understanding of water calculation at specific steps and effects of height changes. This approach runs efficiently in linear time and helps visualize water trapped between bars.

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 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 about water trapped between them.

2. Step 2: Identify what is being calculated

   We calculate how much water can be held between bars after it rains, not just heights or counts.

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 [OK]

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

Common Mistakes:

• Confusing trapped water with max height
• Counting bars taller than neighbors
• Looking for minimum height instead of trapped water

2. Which of the following TypeScript function signatures correctly represents a function to solve the Trapping Rain Water problem?

easy

A. function trap(height: number): number[]

B. function trap(height: number[]): number

C. function trap(height: string): string

D. function trap(height: boolean[]): boolean

Solution

1. Step 1: Analyze the input and output types

   The input is an array of numbers (heights), output is a single number (total trapped water).

2. Step 2: Match the function signature

   Only function trap(height: number[]): number matches input as number array and output as number.

3. Final Answer:

   function trap(height: number[]): number -> Option B

4. Quick Check:

   Input array, output number [OK]

Hint: Input is number array, output is number [OK]

Common Mistakes:

• Using wrong input type like string or boolean
• Returning array instead of number
• Mismatching input and output types

3. What is the output of the following TypeScript code?

function trap(height: number[]): number {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      height[left] >= leftMax ? (leftMax = height[left]) : water += leftMax - height[left];
      left++;
    } else {
      height[right] >= rightMax ? (rightMax = height[right]) : water += rightMax - height[right];
      right--;
    }
  }
  return water;
}

console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]));

medium

A. 6

B. 5

C. 4

D. 7

Solution

1. Step 1: Understand the two-pointer approach

   We use left and right pointers, track max heights, and accumulate trapped water between bars.

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 A

4. Quick Check:

   Two-pointer trap water = 6 [OK]

Hint: Use two-pointer method to calculate trapped water [OK]

Common Mistakes:

• Miscounting trapped water units
• Confusing leftMax and rightMax updates
• Incorrect pointer movement

4. Identify the bug in this TypeScript code snippet for the Trapping Rain Water problem:

function trap(height: number[]): number {
  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 leftMax and rightMax variables are not initialized correctly

B. The water accumulation logic is incorrect

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

D. The pointers left and right are not updated inside the loop

Solution

1. Step 1: Check loop boundary conditions

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

2. Step 2: Correct the loop condition

   Changing to 'left < right' prevents overlap and ensures correct water calculation.

3. Final Answer:

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

4. Quick Check:

   Loop boundary fix = correct water count [OK]

Hint: Use strict less than in loop to avoid double counting [OK]

Common Mistakes:

• Using <= instead of < in while loop
• Not updating pointers inside loop
• Incorrect water calculation logic

5. Given the heights array [4,2,0,3,2,5], what is the total trapped rain water? Use the two-pointer approach to solve.

hard

A. 8

B. 7

C. 6

D. 9

Solution

1. Step 1: Initialize pointers and max heights

   left=0, right=5, leftMax=0, rightMax=0, water=0.

2. Step 2: Move pointers and calculate trapped water

   Iterate:
   - left=0 (height=4) > leftMax=0, update leftMax=4, left++
   - left=1 (height=2) < leftMax=4, water += 4-2=2, left++
   - left=2 (height=0) < leftMax=4, water += 4-0=4, left++
   - left=3 (height=3) < leftMax=4, water += 4-3=1, left++
   - left=4 (height=2) < leftMax=4, water += 4-2=2, left++
   Now left=5 equals right=5, stop.

3. Step 3: Sum trapped water

   Total water = 2+4+1+2 = 9 units.

4. Final Answer:

   9 -> Option D

5. Quick Check:

   Two-pointer trapped water = 9 [OK]

Hint: Calculate trapped water stepwise from both ends [OK]

Common Mistakes:

• Only calculating from one side
• Forgetting to update max heights
• Stopping loop too early