Trapping Rain Water Problem in DSA Javascript - Build from Scratch

Trapping Rain Water Problem

📖 Scenario: Imagine a street with buildings of different heights. When it rains, water gets trapped between these buildings. We want to find out how much water is trapped after the rain stops.

🎯 Goal: You will write a program to calculate the total amount of trapped rainwater given an array of building heights.

📋 What You'll Learn

Create an array called heights with exact values representing building heights

Create two arrays called leftMax and rightMax to store maximum heights from left and right

Use a loop to fill leftMax and rightMax

Calculate total trapped water using the precomputed arrays

Print the total trapped water amount

💡 Why This Matters

🌍 Real World

This problem models how water accumulates in valleys between buildings or hills, useful in urban planning and flood prediction.

💼 Career

Understanding this problem helps in algorithm design, problem-solving skills, and is often asked in technical interviews.

1

Create the building heights array

Create an array called heights with these exact values: [0,1,0,2,1,0,1,3,2,1,2,1]

DSA Javascript

# Your code here

Hint

Use const heights = [...] with the exact numbers inside the brackets.

2

Create arrays for left and right max heights

Create two arrays called leftMax and rightMax with the same length as heights, filled with zeros.

DSA Javascript

const heights = [0,1,0,2,1,0,1,3,2,1,2,1];
// Your code here

Hint

Use new Array(heights.length).fill(0) to create arrays filled with zeros.

3

Fill leftMax and rightMax arrays

Use a for loop with variable i from 1 to heights.length - 1 to fill leftMax where each element is the maximum of leftMax[i-1] and heights[i-1]. Then use a for loop with variable j from heights.length - 2 down to 0 to fill rightMax where each element is the maximum of rightMax[j+1] and heights[j+1].

DSA Javascript

const heights = [0,1,0,2,1,0,1,3,2,1,2,1];
const leftMax = new Array(heights.length).fill(0);
const rightMax = new Array(heights.length).fill(0);
// Your code here

Hint

Use two loops: one forward to fill leftMax, one backward to fill rightMax.

4

Calculate and print total trapped water

Create a variable called totalWater and set it to 0. Use a for loop with variable k from 0 to heights.length - 1 to add to totalWater the value of Math.min(leftMax[k], rightMax[k]) - heights[k] if it is positive. Then print totalWater using console.log(totalWater).

DSA Javascript

const heights = [0,1,0,2,1,0,1,3,2,1,2,1];
const leftMax = new Array(heights.length).fill(0);
const rightMax = new Array(heights.length).fill(0);
for (let i = 1; i = 0; j--) {
    rightMax[j] = Math.max(rightMax[j + 1], heights[j + 1]);
}
// Your code here

Hint

Calculate trapped water at each position by comparing left and right max heights, then sum it up.

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