Trapping Rain Water Problem in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Trapping Rain Water Problem?

To find how much water can be trapped between bars of different heights after raining.

intermediate

What does the 'left max' array represent in the Trapping Rain Water Problem?

It stores the highest bar height from the left up to each position, helping to calculate trapped water.

intermediate

Why do we use both 'left max' and 'right max' arrays in the Trapping Rain Water Problem?

Because trapped water at each position depends on the tallest bars on both left and right sides.

advanced

What is the time complexity of the efficient solution using two pointers for the Trapping Rain Water Problem?

O(n), where n is the number of bars, because we scan the array once with two pointers.

advanced

In the two-pointer approach, what determines which pointer to move?

We move the pointer with the smaller height because trapped water depends on the smaller side.

What does the trapped water at a position depend on?

A The minimum of the tallest bars on the left and right minus the current bar height

B The maximum height of the current bar only

C The sum of all bar heights

D The difference between the tallest bar and the shortest bar

Trapped water depends on the smaller of the tallest bars on both sides minus the current bar height.

Which data structure is commonly used to store the tallest bars from the left and right?

A Stacks

B Queues

C Arrays

D Linked lists

Arrays are used to store left max and right max heights for each position.

What is the space complexity of the solution using left max and right max arrays?

A O(1)

B O(n)

C O(n^2)

D O(log n)

Two arrays of size n are used, so space complexity is O(n).

In the two-pointer approach, what is the initial position of the pointers?

A One at the start and one at the end of the array

B Both at the start

C Both at the end

D Random positions

Two pointers start at the beginning and end of the array and move inward.

Why is the two-pointer approach more space efficient?

A It uses a stack

B It uses extra arrays

C It uses recursion

D It uses only constant extra space

Two-pointer approach uses only variables, so space complexity is O(1).

Explain how the two-pointer approach works to solve the Trapping Rain Water Problem.

Think about comparing heights from both ends and moving pointers accordingly.

Describe why trapped water depends on the minimum of left max and right max heights at each position.

Imagine water filling between walls of different heights.

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