Trapping Rain Water Problem in DSA Typescript - 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: Build a program that calculates the total amount of trapped rainwater between buildings represented by an array of heights.

📋 What You'll Learn

Create an array called heights with exact building heights

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

Calculate trapped water using the heights, leftMax, and rightMax arrays

Print the total trapped water amount

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding this problem helps in roles involving algorithm design, problem solving, and software engineering 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 Typescript

// Create the array heights with the given values
// Your code here

Hint

Use const heights: number[] = [0,1,0,2,1,0,1,3,2,1,2,1]; to create the array.

2

Create leftMax and rightMax arrays

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

DSA Typescript

const heights: number[] = [0,1,0,2,1,0,1,3,2,1,2,1];
// Create leftMax and rightMax arrays filled with zeros
// Your code here

Hint

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

3

Calculate leftMax, rightMax and total trapped water

Fill leftMax with the maximum height to the left of each building, fill rightMax with the maximum height to the right of each building, then calculate the total trapped water in a variable called totalWater.

DSA Typescript

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

Hint

Use two loops to fill leftMax and rightMax. Then use a loop to sum trapped water in totalWater.

4

Print the total trapped water

Print the value of totalWater using console.log.

DSA Typescript

const heights: number[] = [0,1,0,2,1,0,1,3,2,1,2,1];
const leftMax: number[] = new Array(heights.length).fill(0);
const rightMax: number[] = new Array(heights.length).fill(0);

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

let totalWater = 0;
for(let i = 0; i < heights.length; i++) {
    totalWater += Math.min(leftMax[i], rightMax[i]) - heights[i];
}
// Print totalWater
// Your code here

Hint

Use console.log(totalWater); to print the result.

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