Trapping Rain Water Problem in DSA Typescript - 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 two arrays are commonly used to solve the Trapping Rain Water Problem efficiently?

Left max array and right max array, which store the highest bar from the left and right sides for each position.

intermediate

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

Water can only be trapped up to the height of the shorter boundary on either side, so the minimum of left max and right max determines the water level.

beginner

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

O(n), where n is the number of bars, because we scan the array a few times linearly.

beginner

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

O(n) extra space for the two arrays storing left max and right max values.

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

A The highest bar from the left up to each position

B The lowest bar from the left up to each position

C The total water trapped at each position

D The height of the current bar

The 'left max' array stores the maximum height of bars from the left side up to each position.

Why do we take the minimum of left max and right max heights to calculate trapped water at a position?

A Because water level is always zero

B Because water level is limited by the taller boundary

C Because water level equals the current bar height

D Because water level is limited by the shorter boundary

Water can only be trapped up to the height of the shorter boundary on either side.

What is the time complexity of the naive solution that checks all bars on left and right for each position?

A O(n)

B O(n log n)

C O(n^2)

D O(1)

The naive solution checks all bars on left and right for each position, resulting in O(n^2) time.

Which data structure is NOT typically used in the optimal solution for Trapping Rain Water?

A Arrays

B Stacks

C Left max and right max arrays

D Variables to store water sum

Stacks are used in some solutions but not in the common left max/right max array approach.

If the height array is [3, 0, 2, 0, 4], how much water is trapped in total?

A 7

B 6

C 5

D 4

Water trapped is 3 units at index 1, 2 units at index 2, and 1 unit at index 3, total 6.

Describe the step-by-step approach to solve the Trapping Rain Water Problem using left max and right max arrays.

Think about scanning from left and right to find boundaries.

Explain why the trapped water at a position is zero if the current bar is taller than both left max and right max heights.

Consider how water sits between taller bars.

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