Trapping Rain Water Using Stack in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the stack for indices.

DSA Typescript

const stack: number[] = [1];

Drag options to blanks, or click blank then click option'

A{}

Bnull

C0

D[]

Attempts:

3 left

💡 Hint

Common Mistakes

Using {} which creates an object, not an array.

Using null or 0 which are not valid stack initializations.

The stack should be initialized as an empty array to store indices.

2fill in blank

medium

Complete the code to push the current index onto the stack.

DSA Typescript

stack.[1](i);

Drag options to blanks, or click blank then click option'

Ashift

Bpush

Cpop

Dunshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop which removes elements instead of adding.

Using shift or unshift which operate on the start of the array.

To add the current index to the top of the stack, use the push method.

3fill in blank

hard

Fix the error in the condition to check if the stack is not empty.

DSA Typescript

while (stack.[1] > 0 && height[i] > height[stack[stack.length - 1]]) {

Drag options to blanks, or click blank then click option'

Asize

Blength()

Clength

Dcount

Attempts:

3 left

💡 Hint

Common Mistakes

Using length() with parentheses causes a syntax error.

Using size or count which are not valid properties for arrays.

In TypeScript arrays, length is a property, not a method, so use stack.length.

4fill in blank

hard

Fill both blanks to calculate the distance and bounded height for trapped water.

DSA Typescript

const distance = i - stack[stack.length - 1] - [1];
const bounded_height = Math.min(height[i], height[stack[stack.length - 1]]) - height[[2]];

Drag options to blanks, or click blank then click option'

A1

B0

Ctop

Dstack.pop()

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of 1 for distance calculation.

Using stack[stack.length - 1] instead of popped index for height.

Distance is the gap between current index and new top after popping one index (so minus 1). Bounded height is minimum of current and new top heights minus height of popped index.

5fill in blank

hard

Fill all three blanks to add trapped water to the result and update the stack.

DSA Typescript

result += distance * bounded_height;
stack.[1](i);
const top = stack.[2]();
height[top] = Math.max(height[top], height[i]);

Drag options to blanks, or click blank then click option'

Apush

Bpop

Cshift

Dunshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using shift or unshift which operate on the start of the array.

Mixing push and pop order incorrectly.

We add the current index to the stack with push. Then pop the top index to update its height. The last line updates height at popped index.

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