Trapping Rain Water Problem in DSA Javascript - Deep Dive

Overview - Trapping Rain Water Problem

What is it?

The Trapping Rain Water Problem asks how much water can be trapped between bars of different heights after it rains. Imagine each bar as a wall, and water fills the gaps between them. The goal is to find the total amount of water that stays trapped without spilling. This problem helps us understand how to work with arrays and calculate areas using heights.

Why it matters

Without this concept, we wouldn't know how to efficiently calculate trapped water in real-world scenarios like drainage systems or landscape design. It teaches us how to analyze and solve problems involving boundaries and spaces. Without it, we might waste time with slow or incorrect methods, leading to poor designs or resource use.

Where it fits

Before this, learners should understand arrays, loops, and basic problem-solving strategies. After mastering this, they can explore more complex array problems, dynamic programming, and two-pointer techniques.

Mental Model

Core Idea

Water trapped at any position depends on the tallest walls to its left and right, and the trapped water is the difference between the smaller of these two walls and the current height.

Think of it like...

Imagine a row of uneven buckets placed side by side. When you pour water over them, water fills the smaller buckets between taller ones but never spills over the tallest bucket on either side.

Heights:  0   1   0   2   1   0   1   3   2   1   2   1
Bars:    |   |   |   |   |   |   |   |   |   |   |   |
Water:       ~~~~      ~  ~       ~~~~~     ~    ~

Legend:
| = bar height
~ = trapped water units

Build-Up - 6 Steps

1

Foundation

Understanding the Problem Setup

Concept: Introduce the problem and what it means to trap water between bars.

We have an array where each number represents the height of a bar. When it rains, water can collect between these bars. Our task is to find how much water is trapped in total. For example, if the array is [0,1,0,2], water can fill the gap between bars of height 1 and 2.

Result

You understand the problem as finding spaces where water can stay between taller bars.

Understanding the problem visually helps you see why water only stays where there are taller bars on both sides.

2

Foundation

Basic Approach: Checking Each Position

Concept: Calculate trapped water at each position by looking left and right.

For each bar, find the tallest bar to its left and the tallest bar to its right. The water trapped at that bar is the smaller of these two heights minus the bar's own height, if positive. Sum this for all bars to get total trapped water.

Result

You get the total trapped water by summing water at each position.

This method shows the core idea: water depends on boundaries on both sides.

3

Intermediate

Optimizing with Precomputed Arrays

🤔Before reading on: do you think precomputing tallest bars on each side will speed up the solution or slow it down? Commit to your answer.

Concept: Use two arrays to store tallest bars to the left and right for each position to avoid repeated scanning.

Create two arrays: leftMax and rightMax. leftMax[i] stores the tallest bar from the start up to i. rightMax[i] stores the tallest bar from the end up to i. Then calculate trapped water using these arrays in one pass.

Result

The solution runs faster because we avoid scanning left and right for each bar repeatedly.

Precomputing boundaries reduces repeated work, improving efficiency from O(n^2) to O(n).

4

Intermediate

Two-Pointer Technique for Space Efficiency

🤔Before reading on: will using two pointers reduce space usage or increase it? Commit to your answer.

Concept: Use two pointers moving inward from both ends to calculate trapped water without extra arrays.

Initialize two pointers at the start and end of the array. Keep track of the maximum bars seen so far from left and right. Move the pointer with the smaller max inward, calculating trapped water on the fly. This uses constant extra space.

Result

You get the total trapped water with O(n) time and O(1) space.

Two-pointer method cleverly uses the problem's properties to save memory while maintaining speed.

5

Advanced

Handling Edge Cases and Large Inputs

🤔Before reading on: do you think very tall bars at edges trap more water or less? Commit to your answer.

Concept: Understand how bars at edges and uniform heights affect trapped water calculation.

Bars at edges cannot trap water because water spills off. If bars have uniform height, no water is trapped. Large inputs require efficient O(n) solutions to avoid timeouts. The two-pointer method handles these well.

Result

You correctly handle cases with no trapped water and large arrays efficiently.

Recognizing edge cases prevents wrong answers and performance issues in real applications.

6

Expert

Surprising Behavior with Equal Height Bars

🤔Before reading on: does having multiple bars of the same height always increase trapped water? Commit to your answer.

Concept: Explore how equal height bars affect water trapping and why sometimes they don't add to trapped water.

Equal height bars can form flat surfaces that hold water only if surrounded by taller bars. If the bars are all equal height or decreasing, no water is trapped. This subtlety affects how we calculate boundaries and trapped water.

Result

You understand that equal heights don't guarantee trapped water and must be analyzed in context.

Knowing this subtlety helps avoid overestimating trapped water and improves algorithm correctness.

Under the Hood

The algorithm works by comparing the maximum heights on the left and right of each position. Water trapped depends on the smaller of these two maxima minus the current height. Internally, the two-pointer method maintains running maxima and moves pointers inward, updating trapped water without extra arrays. This reduces memory use and speeds up calculation by avoiding repeated scans.

Why designed this way?

Early solutions scanned left and right for each bar, causing slow performance. Precomputing maxima arrays improved speed but used extra space. The two-pointer approach was designed to optimize both time and space by leveraging the insight that trapped water depends on the smaller boundary, allowing a single pass with constant space.

Start -> [left pointer]------------------------[right pointer] <- End

leftMax and rightMax track tallest bars seen so far

Move pointers inward:
If leftMax < rightMax:
  Calculate water at left pointer
  Move left pointer right
Else:
  Calculate water at right pointer
  Move right pointer left

Repeat until pointers meet

Myth Busters - 3 Common Misconceptions

Quick: Does the tallest bar always trap the most water? Commit to yes or no.

Common Belief: The tallest bar traps the most water because it is the highest point.

Reality: The tallest bar itself does not trap water; water is trapped in the valleys between bars. The tallest bar acts as a boundary but holds no water above it.

Why it matters: Believing this leads to incorrect calculations and misunderstanding of where water actually accumulates.

Quick: Is it enough to look only to the left of a bar to find trapped water? Commit to yes or no.

Common Belief: Checking only the tallest bar to the left is enough to calculate trapped water at a position.

Reality: You must consider both left and right tallest bars because water is limited by the smaller of the two boundaries.

Why it matters: Ignoring one side causes overestimation of trapped water, leading to wrong answers.

Quick: Does having equal height bars always increase trapped water? Commit to yes or no.

Common Belief: More bars of the same height always mean more trapped water.

Reality: Equal height bars only trap water if surrounded by taller bars; otherwise, they don't add to trapped water.

Why it matters: Misunderstanding this causes errors in edge cases and incorrect water volume calculations.

Expert Zone

1

When two pointers meet, the trapped water calculation is complete because all positions have been accounted for without overlap.

2

The two-pointer method relies on the invariant that the side with the smaller max boundary determines trapped water at that pointer, a subtle but powerful insight.

3

In some cases, precomputing arrays is faster in practice due to cache locality, despite using more memory.

When NOT to use

This approach is not suitable if the input is streaming or too large to store entirely in memory. In such cases, approximate or online algorithms are needed. Also, if the problem changes to 2D or 3D water trapping, more complex algorithms like priority queues or graph traversal are required.

Production Patterns

In real systems, this problem models drainage and flood simulations. Engineers use optimized two-pointer or segment tree methods for large terrain data. In coding interviews, the two-pointer approach is the standard solution demonstrating mastery of array manipulation and optimization.

Connections

Two-Pointer Technique

Builds-on

Understanding how two pointers move inward based on conditions helps solve many array problems efficiently, including this one.

Dynamic Programming

Related pattern

Precomputing leftMax and rightMax arrays is a form of dynamic programming where we store intermediate results to avoid repeated work.

Hydrology and Landscape Engineering

Real-world application

The problem models how water collects in valleys and basins, helping engineers design drainage systems and predict flood zones.

Common Pitfalls

#1 Calculating trapped water using only the tallest bar on one side.

Wrong approach:

for (let i = 0; i < heights.length; i++) {
let leftMax = Math.max(0, ...heights.slice(0, i));
water += Math.max(0, leftMax - heights[i]);
}

Correct approach:

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

Root cause:

Ignoring the right boundary causes overestimation of trapped water.

#2 Using nested loops to find left and right maxima for each bar, causing slow performance.

Wrong approach:

for (let i = 0; i < n; i++) {
let leftMax = 0;
for (let j = 0; j < i; j++) leftMax = Math.max(leftMax, heights[j]);
let rightMax = 0;
for (let k = i + 1; k < n; k++) rightMax = Math.max(rightMax, heights[k]);
water += Math.max(0, Math.min(leftMax, rightMax) - heights[i]);
}

Correct approach:

Precompute leftMax and rightMax arrays once, then calculate trapped water in a single pass.

Root cause:

Repeated scanning leads to O(n^2) time, inefficient for large inputs.

#3 Not handling edge bars correctly, counting water trapped at edges.

Wrong approach:

Calculate trapped water for all bars including first and last without checks.

Correct approach:

Skip first and last bars or ensure trapped water calculation results in zero for edges.

Root cause:

Edges cannot trap water as there is no boundary on one side.

Key Takeaways

Water trapped at a position depends on the smaller of the tallest bars to its left and right minus its own height.

Precomputing maximum heights on both sides or using two pointers optimizes the solution from slow to efficient.

The two-pointer technique achieves O(n) time and O(1) space by moving inward from both ends.

Edge bars cannot trap water because water spills off the sides, so they must be handled carefully.

Equal height bars do not always increase trapped water; context of surrounding bars matters.

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