Trapping Rain Water Using Stack in DSA Typescript - Execution Trace

Concept Flow - Trapping Rain Water Using Stack

Start with empty stack

↓

Iterate over height array

↓

While stack not empty and current height > height at stack top

↓

Pop top from stack

↓

Calculate trapped water

↓

Push current index to stack

↓

Repeat until end of array

↓

Return total trapped water

We use a stack to keep indices of bars. When a higher bar comes, we pop lower bars and calculate trapped water between bars.

Execution Sample

DSA Typescript

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]]) {
      let top = stack.pop()!;
      if (!stack.length) 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;
}

Calculates trapped rain water using a stack by iterating over bars and computing trapped water when a higher bar is found.

Execution Table

Step	Operation	Current Index (i)	Stack Content (indices)	Popped Index	Distance	Bounded Height	Water Added	Total Water	Visual State
1	Push index 0	0	[0]	-	-	-	0	0	Height: [0] Stack: [0] Water: 0
2	Push index 1	1	[0,1]	-	-	-	0	0	Height: [0,1] Stack: [0,1] Water: 0
3	Push index 2	2	[0,1,2]	-	-	-	0	0	Height: [0,1,0] Stack: [0,1,2] Water: 0
4	Pop index 2, calculate water	3	[0,1]	2	1	1	1	1	Height: [0,1,0,2] Stack after pop: [0,1] Water: 1
5	Pop index 1, calculate water	3	[0]	1	2	1	2	3	Height: [0,1,0,2] Stack after pop: [0] Water: 3
6	Push index 3	3	[0,3]	-	-	-	0	3	Height: [0,1,0,2] Stack: [0,3] Water: 3
7	Push index 4	4	[0,3,4]	-	-	-	0	3	Height: [0,1,0,2,1] Stack: [0,3,4] Water: 3
8	Push index 5	5	[0,3,4,5]	-	-	-	0	3	Height: [0,1,0,2,1,0] Stack: [0,3,4,5] Water: 3
9	Pop index 5, calculate water	6	[0,3,4]	5	1	1	1	4	Height: [0,1,0,2,1,0,1] Stack after pop: [0,3,4] Water: 4
10	Push index 6	6	[0,3,4,6]	-	-	-	0	4	Height: [0,1,0,2,1,0,1] Stack: [0,3,4,6] Water: 4
11	Pop index 6, calculate water	7	[0,3,4]	6	2	0	0	4	Height: [0,1,0,2,1,0,1,3] Stack after pop: [0,3,4] Water: 4
12	Pop index 4, calculate water	7	[0,3]	4	3	1	3	7	Height: [0,1,0,2,1,0,1,3] Stack after pop: [0,3] Water: 7
13	Pop index 3, calculate water	7	[0]	3	5	1	5	12	Height: [0,1,0,2,1,0,1,3] Stack after pop: [0] Water: 12
14	Push index 7	7	[0,7]	-	-	-	0	12	Height: [0,1,0,2,1,0,1,3] Stack: [0,7] Water: 12
15	Push index 8	8	[0,7,8]	-	-	-	0	12	Height: [0,1,0,2,1,0,1,3,2] Stack: [0,7,8] Water: 12
16	Push index 9	9	[0,7,8,9]	-	-	-	0	12	Height: [0,1,0,2,1,0,1,3,2,1] Stack: [0,7,8,9] Water: 12
17	Pop index 9, calculate water	10	[0,7,8]	9	1	1	1	13	Height: [0,1,0,2,1,0,1,3,2,1,2] Stack after pop: [0,7,8] Water: 13
18	Push index 10	10	[0,7,8,10]	-	-	-	0	13	Height: [0,1,0,2,1,0,1,3,2,1,2] Stack: [0,7,8,10] Water: 13
19	Push index 11	11	[0,7,8,10,11]	-	-	-	0	13	Height: [0,1,0,2,1,0,1,3,2,1,2,1] Stack: [0,7,8,10,11] Water: 13
20	End of array reached	-	[0,7,8,10,11]	-	-	-	0	13	Final trapped water: 13

💡 Reached end of height array, total trapped water calculated

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 9	After Step 13	After Step 19	Final
stack	[]	[0]	[0,1,2]	[0,3,4,5]	[0,3]	[0,7,8,10,11]	[0,7,8,10,11]
water	0	0	1	4	12	13	13
i	-	0	2	5	7	11	End

Key Moments - 3 Insights

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

Because trapped water can only be formed when we find a right boundary higher than the bar at stack top. This is shown in execution_table rows 4, 5, 9, 11, 12, 13, and 17 where popping happens only when height[i] > height[stack top].

Why do we check if the stack is empty after popping before calculating distance and bounded height?

If the stack is empty, it means no left boundary exists to trap water, so we cannot calculate trapped water. This is why in the code, after popping, if stack is empty, we break out of the while loop.

How is the distance between bars calculated?

Distance is the horizontal gap between current index and new stack top minus one, representing the width of trapped water. See execution_table row 4 where distance = i - stack top - 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the value of 'water' after adding trapped water?

A 1

B 2

C 0

D 3

💡 Hint

Check the 'Water Added' and 'Total Water' columns at step 4 in execution_table.

At which step does the total trapped water first exceed 4 units?

A Step 9

B Step 13

C Step 19

D Step 20

💡 Hint

Look at the 'Total Water' column in execution_table and find when it first goes above 4.

If the height array had no bars taller than the first bar, how would the stack behave?

A Stack would be empty after first iteration

B Stack would pop frequently

C Stack would keep growing without popping

D Stack would only contain the last index

💡 Hint

Refer to the condition for popping in the code and execution_table rows where popping occurs only if current height > height at stack top.

Concept Snapshot

Trapping Rain Water Using Stack:
- Use a stack to store indices of bars.
- Iterate over bars, pop stack when current bar is higher.
- Calculate trapped water using distance and bounded height.
- Push current index after popping.
- Sum all trapped water and return total.

Full Transcript

This visualization shows how to calculate trapped rain water using a stack. We start with an empty stack and iterate over the height array. For each bar, if it is higher than the bar at the top of the stack, we pop the stack and calculate trapped water between the current bar and the new top of the stack. We keep track of total trapped water. The stack stores indices of bars in non-increasing order of height. When a higher bar is found, trapped water is calculated for bars popped from the stack. This process continues until the end of the array, and the total trapped water is returned.

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