Trapping Rain Water Problem in DSA Typescript

Mental Model

We want to find how much water can stay trapped between bars after it rains, by looking at the heights around each bar.

Analogy: Imagine a row of buildings with different heights. When it rains, water fills the gaps between taller buildings, but only up to the height of the shortest taller building on either side.

Height bars: 3 0 2 0 4
Visual: 4|       ↑
       3| ↑     ↑
       2|   ↑   ↑
       1|       
       0|_ _ _ _ _
Indexes: 0 1 2 3 4

Dry Run Walkthrough

Input: heights: [3, 0, 2, 0, 4]

Goal: Calculate total trapped water between bars

Step 1: Calculate max height to the left of each bar

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

Why: We need to know the tallest bar on the left to know water limit

Step 2: Calculate max height to the right of each bar

rightMax = [4, 4, 4, 4, 4]

Why: We need to know the tallest bar on the right to know water limit

Step 3: Calculate trapped water at each bar by min(leftMax, rightMax) - height

water trapped per bar = [0, 3, 1, 3, 0]

Why: Water level is limited by shorter side, minus bar height

Step 4: Sum trapped water values

total trapped water = 7

Why: Sum gives total water trapped between bars

Result:

Total trapped water = 7 units

Annotated Code

DSA Typescript

class TrappingRainWater {
  static trap(height: number[]): number {
    const n = height.length;
    if (n === 0) return 0;

    const leftMax: number[] = new Array(n).fill(0);
    const rightMax: number[] = new Array(n).fill(0);

    leftMax[0] = height[0];
    for (let i = 1; i < n; i++) {
      leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    }

    rightMax[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; i--) {
      rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    }

    let trappedWater = 0;
    for (let i = 0; i < n; i++) {
      trappedWater += Math.min(leftMax[i], rightMax[i]) - height[i];
    }

    return trappedWater;
  }
}

const heights = [3, 0, 2, 0, 4];
const result = TrappingRainWater.trap(heights);
console.log(`Total trapped water = ${result}`);

leftMax[0] = height[0];

initialize left max with first bar height

for (let i = 1; i < n; i++) { leftMax[i] = Math.max(leftMax[i - 1], height[i]); }

build left max array by tracking tallest bar from left

rightMax[n - 1] = height[n - 1];

initialize right max with last bar height

for (let i = n - 2; i >= 0; i--) { rightMax[i] = Math.max(rightMax[i + 1], height[i]); }

build right max array by tracking tallest bar from right

for (let i = 0; i < n; i++) { trappedWater += Math.min(leftMax[i], rightMax[i]) - height[i]; }

calculate trapped water at each bar and sum

Output

Total trapped water = 7

Complexity Analysis

Time: O(n) because we scan the height array a few times linearly

Space: O(n) because we store leftMax and rightMax arrays of size n

vs Alternative: Compared to brute force O(n^2) checking each bar's left and right max repeatedly, this is much faster

Edge Cases

empty height array

returns 0 because no bars means no trapped water

DSA Typescript

if (n === 0) return 0;

all bars same height

returns 0 because no space to trap water

DSA Typescript

trappedWater += Math.min(leftMax[i], rightMax[i]) - height[i];

strictly increasing or decreasing bars

returns 0 because water cannot be trapped on edges

DSA Typescript

trappedWater += Math.min(leftMax[i], rightMax[i]) - height[i];

When to Use This Pattern

When you see a problem asking how much water can be trapped between bars or heights, use the trapping rain water pattern with precomputed max heights on both sides.

Common Mistakes

Mistake: Forgetting to handle empty input array
Fix: Add a check at start to return 0 if array length is zero

Mistake: Using min(leftMax, rightMax) without subtracting current height
Fix: Always subtract current bar height to get trapped water at that position

Mistake: Calculating leftMax and rightMax inside the trapped water loop
Fix: Precompute leftMax and rightMax arrays before summing trapped water

Summary

Calculates how much water is trapped between bars after rain.

Use when given an array of bar heights and asked total trapped water.

The trapped water at each bar depends on the shortest tallest bar on its left and right.

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