Trapping Rain Water Problem in DSA Typescript - Time & Space Complexity

Time Complexity: Trapping Rain Water Problem

O(n)

Understanding Time Complexity

We want to understand how the time needed to solve the Trapping Rain Water problem changes as the input size grows.

Specifically, how the number of operations depends on the number of bars in the elevation map.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right--;
    }
  }
  return water;
}
    

This code calculates how much water can be trapped between bars represented by the array height.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single while loop that moves two pointers from both ends towards the center.
• How many times: The loop runs at most n times, where n is the number of bars.

How Execution Grows With Input

As the number of bars increases, the loop runs once per bar, so the total operations grow directly with input size.

Input Size (n)	Approx. Operations
10	About 10 loop steps
100	About 100 loop steps
1000	About 1000 loop steps

Pattern observation: The number of steps grows linearly with the number of bars.

Final Time Complexity

Time Complexity: O(n)

This means the time to find trapped water grows in direct proportion to the number of bars.

Common Mistake

[X] Wrong: "Because there are two pointers, the time complexity is doubled or quadratic."

[OK] Correct: Both pointers move inward without repeating positions, so total steps are still proportional to n, not n squared.

Interview Connect

Understanding this problem's time complexity shows you can analyze two-pointer techniques efficiently, a skill useful in many coding challenges.

Self-Check

"What if we used nested loops to check water trapped at each bar? How would the time complexity change?"

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