Trapping Rain Water Problem in DSA Typescript - 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 spaces between them. The goal is to find the total amount of water that stays trapped without spilling over. This problem helps us understand how to work with arrays and calculate areas between heights.

Why it matters

Without this concept, we would struggle to solve real-world problems like calculating water storage, flood prediction, or even designing drainage systems. It teaches us how to analyze and process data efficiently to find hidden patterns. Without it, many practical applications involving space and volume calculations would be much harder and slower.

Where it fits

Before this, you should understand arrays, loops, and basic problem-solving with data structures. After mastering this, you can explore more complex algorithms like dynamic programming, stack-based problems, and two-pointer techniques. It fits into the broader topic of array manipulation and optimization.

Mental Model

Core Idea

Water trapped above a bar depends on the tallest bars to its left and right, and the trapped water is the minimum of these heights minus the bar's own height.

Think of it like...

Imagine a row of buildings with different heights after a rainstorm. Water collects in the valleys between taller buildings, but only up to the height of the shortest building on either side. The trapped water is like puddles formed in these valleys.

Index:  0   1   2   3   4   5   6   7
Height: [0,  1,  0,  2,  1,  0,  1,  3]

Water trapped at each index depends on:
  Left max height:  ↑
  Right max height: ↓

Diagram:
  Height: 3 |           ■
           2 |       ■   ■
           1 |   ■   ■ ■ ■
           0 | ■ ■ ■ ■ ■ ■ ■
           Index: 0 1 2 3 4 5 6 7

Build-Up - 6 Steps

1

Foundation

Understanding the Problem Setup

Concept: Introduce the problem scenario with bars and water trapping.

We have an array where each number represents the height of a bar. When it rains, water can get trapped between these bars. Our task is to find how much water is trapped in total. For example, given heights [0,1,0,2], water can be trapped at index 2 because it is lower than bars at index 1 and 3.

Result

You understand the problem setup and what input and output look like.

Understanding the physical setup helps connect the abstract array to a real-world scenario, making the problem easier to visualize.

2

Foundation

Brute Force Approach to Water Calculation

Concept: Calculate trapped water at each bar by checking max heights on left and right.

For each bar, find the tallest bar on its left and the tallest bar on its right. The water trapped on that bar is the smaller of these two heights minus the bar's own height (if positive). Sum this for all bars. This method uses nested loops.

Result

For input [0,1,0,2], trapped water is 1 unit at index 2.

This approach shows the direct logic but is inefficient, highlighting the need for optimization.

3

Intermediate

Using Precomputed Left and Right Max Arrays

🤔Before reading on: do you think precomputing max heights on both sides will reduce repeated work? Commit to yes or no.

Concept: Store max heights to the left and right of each bar in separate arrays 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, for each bar, trapped water = min(leftMax[i], rightMax[i]) - height[i]. This reduces time complexity to linear.

Result

For input [0,1,0,2], leftMax = [0,1,1,2], rightMax = [2,2,2,2], trapped water total = 1.

Precomputing saves time by avoiding repeated scans, a common optimization pattern in array problems.

4

Intermediate

Two-Pointer Technique for Space Optimization

🤔Before reading on: can we find trapped water using two pointers without extra arrays? Commit to yes or no.

Concept: Use two pointers moving inward from both ends, tracking max heights on the fly to calculate trapped water with constant extra space.

Initialize two pointers: left at start, right at end. Keep track of leftMax and rightMax as you move pointers inward. At each step, move the pointer with smaller height, update max, and add trapped water if current bar is lower than max. This method uses O(1) extra space and O(n) time.

Result

For input [0,1,0,2], trapped water calculated correctly as 1 with two pointers.

Two-pointer technique cleverly reduces space usage while maintaining efficiency, a powerful pattern in array problems.

5

Advanced

Stack-Based Approach for Trapping Water

🤔Before reading on: do you think a stack can help find boundaries for trapped water? Commit to yes or no.

Concept: Use a stack to keep track of bars that form boundaries and calculate trapped water when a taller bar is found.

Traverse the array, pushing indices onto a stack while bars are decreasing. When a taller bar appears, pop from stack and calculate trapped water between current bar and new top of stack. Repeat until current bar is not taller. This approach handles complex cases efficiently.

Result

For input [0,1,0,2], stack method calculates trapped water as 1.

Stack approach reveals how to dynamically find boundaries and trapped water, useful for related problems involving next greater elements.

6

Expert

Handling Edge Cases and Large Inputs Efficiently

🤔Before reading on: do you think the two-pointer method always outperforms others in practice? Commit to yes or no.

Concept: Understand how to handle edge cases like flat bars, no trapping, and very large inputs with optimized methods.

Edge cases include all bars equal height (no water), strictly increasing or decreasing bars (no water), and very large arrays. Two-pointer method is preferred for large inputs due to O(1) space. Also, consider integer overflow in some languages and ensure safe calculations.

Result

Efficient and correct water trapping calculation even for large or tricky inputs.

Knowing edge cases and performance trade-offs ensures robust, production-ready solutions.

Under the Hood

The trapped water at each position depends on the tallest bars to the left and right. Internally, the algorithm compares these heights and subtracts the current bar's height to find water volume. The two-pointer method maintains running max heights and moves pointers inward, updating trapped water without extra arrays. The stack method uses a last-in-first-out structure to find boundaries dynamically, popping bars when a taller bar is found to calculate trapped water between boundaries.

Why designed this way?

Early brute force was simple but slow. Precomputing max arrays improved speed but used extra space. The two-pointer method was designed to optimize space while keeping linear time, a tradeoff important in memory-limited environments. The stack approach was introduced to handle complex patterns and is inspired by similar problems like next greater element, showing algorithmic creativity.

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

Two-pointer approach:

Left pointer -> 0
Right pointer -> 7

leftMax = 0, rightMax = 3

Step 1: height[left]=0 < height[right]=3
  leftMax = max(0,0)=0
  trapped water at left=0
  move left to 1

Step 2: height[left]=1 < height[right]=3
  leftMax = max(0,1)=1
  trapped water at left=0
  move left to 2

Step 3: height[left]=0 < height[right]=3
  leftMax=1
  trapped water at left=1-0=1
  move left to 3

... continue until pointers meet.

Myth Busters - 4 Common Misconceptions

Quick: Does the tallest bar always trap the most water? Commit 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 valleys between bars. The amount depends on the shortest boundary on either side, not just the tallest bar.

Why it matters: Misunderstanding this leads to wrong calculations and missed trapped water in valleys, causing incorrect results.

Quick: Is it enough to check only one side's max height to find trapped water? Commit yes or no.

Common Belief: Checking the tallest bar on one side is enough to calculate trapped water.

Reality: You must consider both left and right tallest bars because water level is limited by the shorter one.

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

Quick: Does the brute force method run efficiently on large inputs? Commit yes or no.

Common Belief: Brute force is fine for all input sizes since it is straightforward.

Reality: Brute force has O(n^2) time complexity and becomes very slow for large inputs, making it impractical.

Why it matters: Using brute force on large data causes performance issues and timeouts in real applications.

Quick: Can the two-pointer method be used if the array is not sorted? Commit yes or no.

Common Belief: Two-pointer method requires sorted arrays to work correctly.

Reality: The two-pointer method works on any array of heights regardless of order, as it relies on max heights, not sorting.

Why it matters: Thinking sorting is needed wastes time and leads to unnecessary complexity.

Expert Zone

1

The two-pointer method's correctness depends on always moving the pointer with the smaller height, ensuring trapped water is counted accurately.

2

Stack-based approach can be adapted to solve related problems like finding the largest rectangle in a histogram, showing its versatility.

3

Precomputing max arrays trades space for time, which is a classic example of space-time tradeoff in algorithms.

When NOT to use

Avoid brute force for large inputs due to poor performance. If memory is very limited, prefer two-pointer over precomputed arrays. Stack method is more complex and may not be necessary for simple cases. For streaming data or dynamic updates, specialized data structures like segment trees may be better.

Production Patterns

In real systems, the two-pointer method is preferred for its balance of speed and memory. Precomputed arrays are used when memory is abundant and code simplicity is desired. Stack approach is used in complex scenarios or when extending to related problems. Handling edge cases and input validation is critical in production.

Connections

Two-Pointer Technique

Builds-on

Understanding trapping rain water deepens grasp of two-pointer technique, a powerful pattern for solving array problems efficiently.

Stack Data Structure

Same pattern

The stack approach to trapping rain water shares logic with next greater element problems, showing how stacks help find boundaries in sequences.

Hydrology and Flood Modeling

Application domain

The problem models how water collects in terrain depressions, linking computer algorithms to environmental science and engineering.

Common Pitfalls

#1 Calculating trapped water using only one side's max height.

Wrong approach:

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

Correct approach:

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

Root cause:

Ignoring the right boundary causes overestimation of trapped water.

#2 Using nested loops without optimization on large inputs.

Wrong approach:

for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// find max left and right for each i
}
}

Correct approach:

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

Root cause:

Not optimizing repeated work leads to slow performance.

#3 Moving the wrong pointer in two-pointer method.

Wrong approach:

if (height[left] > height[right]) {
left++;
} else {
right--;
}

Correct approach:

if (height[left] < height[right]) {
left++;
} else {
right--;
}

Root cause:

Moving the pointer with the larger height breaks the logic of trapped water calculation.

Key Takeaways

Trapped water at each bar depends on the minimum of the tallest bars on its left and right minus its own height.

Precomputing max heights or using two pointers optimizes the solution from quadratic to linear time.

The two-pointer method is space-efficient and preferred for large inputs.

Stack-based approach offers a dynamic way to find boundaries and is useful for related problems.

Understanding edge cases and pointer movement rules is crucial for correct and efficient implementation.

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