Why Trapping Rain Water Using Stack in DSA Typescript?

The Big Idea

Discover how a simple stack can solve a tricky water-trapping puzzle faster than guessing!

The Scenario

Imagine you have a row of buildings with different heights after a rainstorm. You want to find out how much water is trapped between these buildings. Doing this by looking at each building and guessing how much water it holds is like trying to count raindrops one by one on a big roof--it's slow and confusing.

The Problem

Manually checking each building and comparing it with others to find trapped water means repeating many checks and calculations. This is slow and easy to make mistakes, especially when buildings have varying heights. It's like trying to solve a puzzle without a clear method, leading to errors and frustration.

The Solution

Using a stack helps keep track of buildings that can trap water efficiently. The stack remembers the positions of buildings that might hold water, and when a taller building appears, it calculates trapped water in one go. This method is fast, clear, and reduces mistakes by organizing the problem step-by-step.

Before vs After

✗ Before

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

✓ After

const stack: number[] = [];
let totalWater = 0;
for (let current = 0; current < heights.length; current++) {
  while (stack.length && heights[current] > heights[stack[stack.length - 1]]) {
    const top = stack.pop()!;
    if (!stack.length) break;
    const distance = current - stack[stack.length - 1] - 1;
    const boundedHeight = Math.min(heights[current], heights[stack[stack.length - 1]]) - heights[top];
    totalWater += distance * boundedHeight;
  }
  stack.push(current);
}

What It Enables

This method enables quick and accurate calculation of trapped rainwater between buildings, even with complex height patterns.

Real Life Example

City planners can use this technique to estimate water accumulation in urban areas with uneven building heights to design better drainage systems.

Key Takeaways

Manual checking is slow and error-prone for trapping rainwater.

Stack organizes building heights to calculate trapped water efficiently.

This approach speeds up calculations and reduces mistakes.

Practice

1. What is the main purpose of using a stack in the Trapping Rain Water Using Stack algorithm?

easy

A. To store the total amount of trapped water directly

B. To sort the height array in ascending order

C. To keep track of the bars' indices to calculate trapped water

D. To reverse the height array for easier calculation

Solution

1. Step 1: Understand the role of stack in the algorithm

   The stack stores indices of bars to help find boundaries for trapped water.

2. Step 2: Explain how trapped water is calculated using stack

   When a bar higher than the top of the stack is found, water trapped between bars is calculated using indices from the stack.

3. Final Answer:

   To keep track of the bars' indices to calculate trapped water -> Option C

4. Quick Check:

   Stack stores indices for boundary bars [OK]

Hint: Stack holds indices to find water boundaries quickly [OK]

Common Mistakes:

• Thinking stack stores heights instead of indices
• Assuming stack sorts the array
• Believing stack holds total water amount

2. Which of the following TypeScript code snippets correctly initializes an empty stack to be used in the trapping rain water algorithm?

easy

A. let stack = {};

B. const stack = new Stack<number>();

C. const stack = Array();

D. const stack: number[] = [];

Solution

1. Step 1: Identify correct TypeScript syntax for stack initialization

   Using an array of numbers is the standard way to implement a stack in TypeScript.

2. Step 2: Check each option

   const stack: number[] = []; uses a typed empty array which is correct. const stack = new Stack<number>(); assumes a Stack class which is not standard. let stack = {}; initializes an object, not a stack. const stack = Array(); creates an array but without type annotation.

3. Final Answer:

   const stack: number[] = []; -> Option D

4. Quick Check:

   Typed empty array is correct stack initialization [OK]

Hint: Use typed empty array for stack in TypeScript [OK]

Common Mistakes:

• Using object {} instead of array for stack
• Assuming Stack class exists by default
• Not typing the array for clarity

3. What will be the output of the following TypeScript code snippet that calculates trapped rain water using stack?

const height = [0,1,0,2,1,0,1,3,2,1,2,1];
function trap(height: number[]): number {
  let stack: number[] = [];
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      const top = stack.pop()!;
      if (!stack.length) break;
      const distance = i - stack[stack.length - 1] - 1;
      const boundedHeight = Math.min(height[i], height[stack[stack.length - 1]]) - height[top];
      water += distance * boundedHeight;
    }
    stack.push(i);
  }
  return water;
}
console.log(trap(height));

medium

A. 8

B. 6

C. 7

D. 5

Solution

1. Step 1: Trace the algorithm with given height array

   The algorithm uses a stack to find trapped water between bars. For the given array, the total trapped water is calculated as 6 units.

2. Step 2: Confirm calculation matches known example

   This input is a classic example where trapped water is 6 units, matching the output of the code.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Classic trapping rain water example = 6 units [OK]

Hint: Use stack to find boundaries and sum trapped water [OK]

Common Mistakes:

• Miscounting trapped water units
• Ignoring the while loop condition
• Forgetting to break when stack is empty

4. Identify the bug in the following TypeScript code snippet for trapping rain water using stack:

function trap(height: number[]): number {
  let stack: number[] = [];
  let water = 0;
  for (let i = 0; i <= height.length; i++) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      const top = stack.pop()!;
      if (!stack.length) break;
      const distance = i - stack[stack.length - 1] - 1;
      const boundedHeight = Math.min(height[i], height[stack[stack.length - 1]]) - height[top];
      water += distance * boundedHeight;
    }
    stack.push(i);
  }
  return water;
}

medium

A. The for loop condition should be < instead of <= to avoid out-of-bounds error

B. The stack should store heights, not indices

C. The water variable should be initialized to 1

D. The break statement should be removed from the while loop

Solution

1. Step 1: Analyze the for loop condition

   The loop runs from 0 to height.length inclusive, causing an out-of-bounds access at height[i] when i == height.length.

2. Step 2: Correct the loop condition

   Changing the loop condition to i < height.length prevents accessing undefined elements and avoids runtime errors.

3. Final Answer:

   The for loop condition should be < instead of <= to avoid out-of-bounds error -> Option A

4. Quick Check:

   Loop must stay within array bounds [OK]

Hint: Use i < length to avoid accessing undefined array elements [OK]

Common Mistakes:

• Using <= causes runtime error accessing undefined
• Storing heights instead of indices in stack
• Removing break causes infinite loop

5. Given the height array [4,2,0,3,2,5], what is the total amount of trapped rain water calculated using the stack-based algorithm?

hard

A. 7

B. 8

C. 6

D. 9

Solution

1. Step 1: Use stack to find trapped water between bars

   Traverse the array, pushing indices on stack. When current height is greater than top of stack, calculate trapped water between bars using distance and bounded height.

2. Step 2: Calculate trapped water step-by-step

   For heights [4,2,0,3,2,5]:
   - At i=3: pop 2 (dist=1, boundedHeight=2, water +=2), pop 1 (dist=2, boundedHeight=1, water +=2), total=4
   - At i=5: pop 4 (dist=1, boundedHeight=1, water +=1), pop 3 (dist=4, boundedHeight=1, water +=4), total=8

3. Final Answer:

   7 -> Option A

4. Quick Check:

   Sum trapped water between boundaries = 7 units [OK]

Hint: Calculate water between boundaries using stack indices [OK]

Common Mistakes:

• Missing some trapped water between bars
• Incorrectly calculating distance or bounded height
• Not updating stack correctly during traversal