Trapping Rain Water Using Stack in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a stack to solve the Trapping Rain Water problem?

Use a stack to keep track of bars that are bounded by taller bars on both sides. When a taller bar is found, calculate trapped water with the bars in the stack.

beginner

In the stack approach, what does each element in the stack represent?

Each element represents the index of a bar in the height array, used to find boundaries for trapped water.

intermediate

Why do we pop from the stack when the current bar height is greater than the height of the bar at the top of the stack?

Because we found a right boundary taller than the top bar, allowing calculation of trapped water between the left boundary and current bar.

intermediate

How is the trapped water volume calculated between two bars using the stack method?

Trapped water = (distance between bars - 1) * (min height of left and right bars - height of bottom bar).

intermediate

What is the time complexity of the Trapping Rain Water problem using the stack approach?

O(n), where n is the number of bars, because each bar is pushed and popped at most once.

What data structure is used to solve the Trapping Rain Water problem efficiently?

A Queue

B Linked List

C Stack

D Hash Map

Stack helps track bars and boundaries to calculate trapped water efficiently.

When do we calculate trapped water in the stack approach?

A When current bar is taller than top of stack

B When current bar is shorter than top of stack

C When stack is empty

D At the end of the array only

We calculate trapped water when we find a taller bar that forms a right boundary.

What does the 'distance' represent in trapped water calculation?

A Number of bars between left and right boundaries minus one

B Height difference between bars

C Sum of heights of bars

D Index of current bar

Distance is the horizontal gap between boundaries minus one bar.

What happens to the stack when a bar is popped during calculation?

A It is ignored

B It is the left boundary

C It is the right boundary

D It represents the bottom of a water container

The popped bar is the bottom between two boundaries trapping water.

What is the space complexity of the stack approach for Trapping Rain Water?

A O(1)

B O(n)

C O(log n)

D O(n^2)

Stack can hold up to n bars in worst case, so space is O(n).

Explain step-by-step how the stack is used to calculate trapped rain water.

Think about how boundaries and bottom bars form water containers.

Describe how trapped water volume is computed between two bars using the stack method.

Focus on the shape formed by bars and water trapped inside.

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