Trapping Rain Water Using Stack in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trapping Rain Water Calculation

What is the output of the following TypeScript code that calculates trapped rain water using a stack?

DSA Typescript

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

console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]));

A 5

B 6

C 7

D 8

💡 Hint

Think about how the stack helps find boundaries to trap water between bars.

The code uses a stack to find the left and right boundaries for trapped water. It calculates the trapped water volume correctly for the given input, which is 6 units.

🧠 Conceptual

intermediate

Understanding Stack Usage in Trapping Rain Water

Why is a stack used in the trapping rain water problem instead of a simple two-pointer approach?

A Stack helps track indices of bars to find boundaries dynamically as we scan from left to right.

B Stack sorts the bars by height to calculate trapped water easily.

C Stack stores the water volume directly for each bar.

D Stack is used to reverse the array for easier calculation.

💡 Hint

Think about how the stack helps find the previous smaller or taller bars.

The stack stores indices of bars in a way that helps find left and right boundaries dynamically while scanning the array once.

🔧 Debug

advanced

Identify the Error in Trapping Rain Water Stack Code

What error will this TypeScript code produce when run?

DSA Typescript

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

console.log(trap([4,2,0,3,2,5]));

A No error, outputs 9

B TypeError due to undefined top

C Outputs 8 incorrectly

D SyntaxError due to missing exclamation mark

💡 Hint

Check how the top variable is handled after popping from stack.

The code uses a non-null assertion operator (!) correctly after popping from stack, so no TypeError occurs. The output is 9 for the input.

❓ Predict Output

advanced

Resulting Stack State After Processing Input

What is the state of the stack (indices) after processing the entire input array in this trapping rain water code?

DSA Typescript

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

console.log(trap([3,0,2,0,3]));

A [0,1,2,3,4]

B [4]

C [0,2,4]

D [0,4]

💡 Hint

The stack holds indices of bars that have not been fully processed or bounded.

After processing, the stack contains indices 0 and 4 representing bars that form boundaries with no higher bar to the right.

🧠 Conceptual

expert

Why Does the Stack-Based Algorithm Run in O(n) Time?

Why does the stack-based trapping rain water algorithm run in linear time despite having nested loops?

A The stack is implemented as a balanced tree, optimizing operations.

B The inner loop runs only for half of the elements, reducing complexity.

C Each element is pushed and popped at most once, so total operations are proportional to n.

D The algorithm uses memoization to avoid repeated calculations.

💡 Hint

Consider how many times each index is pushed and popped from the stack.

Each bar index is pushed once and popped once, so total stack operations are at most 2n, making the algorithm O(n).

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