Trapping Rain Water Problem in DSA Javascript

Mental Model

We want to find how much water can be trapped between bars of different heights after it rains. Water is trapped where shorter bars are between taller bars.

Analogy: Imagine a row of buildings with different heights. When it rains, water collects in the valleys between taller buildings, just like water trapped between bars.

Height bars: 3 -> 0 -> 2 -> 0 -> 4
Water trapped:   ~     ~     ~
Visual: 3 ↑
        |   2 ↑
        |   |   4 ↑
Bars: 3 -> 0 -> 2 -> 0 -> 4 -> null

Dry Run Walkthrough

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

Goal: Calculate total water trapped between bars after raining

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

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

Why: We need left boundaries to know how high water can be trapped from the left side

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

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

Why: We need right boundaries to know how high water can be trapped from the right side

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 the shorter boundary on either side minus the bar height

Step 4: Sum all trapped water amounts

total water trapped = 7

Why: Total trapped water is sum of water above each bar

Result:

3 -> 0 -> 2 -> 0 -> 4 -> null
Total trapped water = 7

Annotated Code

DSA Javascript

class TrappingRainWater {
  static trap(height) {
    if (height.length === 0) return 0;
    const n = height.length;
    const leftMax = new Array(n).fill(0);
    const rightMax = new Array(n).fill(0);
    let water = 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]);
    }

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

    return water;
  }
}

const heights = [3, 0, 2, 0, 4];
const result = TrappingRainWater.trap(heights);
console.log(heights.join(' -> ') + ' -> null');
console.log('Total trapped water = ' + result);

leftMax[0] = height[0];

initialize left max boundary 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 highest bar from left

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

initialize right max boundary 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 highest bar from right

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

calculate trapped water at each bar by min boundary minus height

Output

3 -> 0 -> 2 -> 0 -> 4 -> null

Total trapped water = 7

Complexity Analysis

Time: O(n) because we traverse the height array three times to build leftMax, rightMax, and calculate water

Space: O(n) because we use two extra arrays leftMax and rightMax of size n

vs Alternative: Compared to a naive approach that checks left and right max for each bar separately (O(n^2)), this method is much faster by precomputing boundaries

Edge Cases

empty array

returns 0 because no bars means no water trapped

DSA Javascript

if (height.length === 0) return 0;

all bars same height

returns 0 because no valleys to trap water

DSA Javascript

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

strictly increasing or decreasing bars

returns 0 because water cannot be trapped without a valley

DSA Javascript

water += 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 by precomputing max boundaries from left and right.

Common Mistakes

Mistake: Calculating trapped water using only one side's max height
Fix: Use the minimum of left max and right max heights to find water level

Mistake: Not handling empty input array
Fix: Add a guard clause to return 0 if input array is empty

Mistake: Overwriting water trapped without summing all bars
Fix: Accumulate trapped water for each bar by adding to total

Summary

Calculates total water trapped between bars after raining by using left and right max boundaries.

Use when you need to find how much water can be trapped between heights or bars.

The key insight is that water level at each bar is limited by the shorter boundary on either side.

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