Trapping Rain Water Using Stack in DSA Typescript - Build from Scratch

Trapping Rain Water Using Stack

📖 Scenario: Imagine you have a row of buildings with different heights. When it rains, water can get trapped between these buildings. We want to find out how much water is trapped after it rains.

🎯 Goal: Build a program that uses a stack to calculate the total amount of trapped rainwater between buildings of different heights.

📋 What You'll Learn

Create an array called heights with exact values representing building heights

Create a stack to help calculate trapped water

Use a loop to process each building height and calculate trapped water using the stack

Print the total trapped water amount

💡 Why This Matters

🌍 Real World

Calculating trapped rainwater helps in urban planning and drainage system design to prevent flooding.

💼 Career

Understanding stack-based algorithms and problem-solving skills is useful for software engineering roles involving data structures and algorithm challenges.

1

Create the building heights array

Create an array called heights with these exact values: [0,1,0,2,1,0,1,3,2,1,2,1]

DSA Typescript

// Create the array heights with the given values
// Your code here

Hint

Use const heights = [0,1,0,2,1,0,1,3,2,1,2,1]; to create the array.

2

Initialize stack and water counter

Create a variable called stack as an empty array of numbers and a variable called water set to 0

DSA Typescript

const heights = [0,1,0,2,1,0,1,3,2,1,2,1];
// Create stack as empty number array
// Create water variable set to 0
// Your code here

Hint

Use const stack: number[] = []; and let water = 0;.

3

Calculate trapped water using stack

Use a for loop with variable i from 0 to heights.length. Inside the loop, use a while loop to pop from stack while heights[i] is greater than heights[stack[stack.length - 1]]. Calculate trapped water inside the while loop and add it to water. Push i to stack at the end of each for iteration.

DSA Typescript

const heights = [0,1,0,2,1,0,1,3,2,1,2,1];
const stack: number[] = [];
let water = 0;
// Use for loop with i from 0 to heights.length
// Inside for loop, use while loop to pop from stack while heights[i] > heights[stack top]
// Calculate trapped water inside while loop and add to water
// Push i to stack
// Your code here

Hint

Use a for loop and inside it a while loop to pop from stack and calculate trapped water.

4

Print the total trapped water

Write console.log(water) to print the total trapped water amount.

DSA Typescript

const heights = [0,1,0,2,1,0,1,3,2,1,2,1];
const stack: number[] = [];
let water = 0;

for (let i = 0; i  0 && heights[i] > heights[stack[stack.length - 1]]) {
        const top = stack.pop()!;
        if (stack.length === 0) {
            break;
        }
        const distance = i - stack[stack.length - 1] - 1;
        const boundedHeight = Math.min(heights[i], heights[stack[stack.length - 1]]) - heights[top];
        water += distance * boundedHeight;
    }
    stack.push(i);
}
// Print the total trapped water
// Your code here

Hint

Use console.log(water) to show the result.

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