Trapping Rain Water Using Stack in DSA Typescript

Mental Model

We use a stack to remember bars that might trap water when a taller bar comes after them. The stack helps find boundaries to calculate trapped water between bars.

Analogy: Imagine a row of buildings with different heights. When rain falls, water collects in valleys between taller buildings. The stack helps us find these valleys by remembering buildings until a taller one appears.

Height bars: 0 1 0 2 1 0 1 3 2 1 2 1
Stack stores indices of bars that might trap water
Example: [0] -> [1] -> [3] -> null

Dry Run Walkthrough

Input: height array: [0,1,0,2,1,0,1,3,2,1,2,1]

Goal: Calculate total trapped rain water between bars using a stack

Step 1: Push index 0 (height 0) onto stack

Stack: [0]
Water trapped: 0

Why: Start with first bar to compare with next bars

Step 2: Push index 1 (height 1) since it's taller than height at stack top (0)

Stack: [0,1]
Water trapped: 0

Why: We need a taller bar to form a boundary for trapping water

Step 3: Index 2 (height 0) is lower, push it onto stack

Stack: [0,1,2]
Water trapped: 0

Why: Lower bar might form a valley for future trapping

Step 4: Index 3 (height 2) is taller than top of stack (height 0 at index 2), pop index 2

Stack after pop: [0,1]
Calculate trapped water between index 1 and 3
Distance = 3 - 1 - 1 = 1
Bounded height = min(height[1], height[3]) - height[2] = min(1,2)-0=1
Water trapped += 1*1=1

Why: Found a valley bounded by bars at indices 1 and 3 trapping 1 unit water

Step 5: Index 3 (height 2) still taller than top of stack (height 1 at index 1), pop index 1

Stack after pop: [0]
Calculate trapped water between index 0 and 3
Distance = 3 - 0 - 1 = 2
Bounded height = min(height[0], height[3]) - height[1] = min(0,2)-1 = -1 (no water)

Why: No water trapped because left boundary is lower

Step 6: Push index 3 (height 2) onto stack

Stack: [0,3]
Water trapped: 1

Why: New taller bar becomes boundary for future trapping

Step 7: Push index 4 (height 1) since it's lower than top of stack (height 2)

Stack: [0,3,4]
Water trapped: 1

Why: Lower bar might trap water later

Step 8: Index 5 (height 0) lower, push onto stack

Stack: [0,3,4,5]
Water trapped: 1

Why: Keep track of valley bottom

Step 9: Index 6 (height 1) taller than top of stack (height 0 at index 5), pop index 5

Stack after pop: [0,3,4]
Distance = 6 - 4 - 1 = 1
Bounded height = min(height[4], height[6]) - height[5] = min(1,1)-0=1
Water trapped += 1*1=1 (total 2)

Why: Water trapped in small valley between indices 4 and 6

Step 10: Index 6 (height 1) not taller than top of stack (height 1 at index 4), push index 6

Stack: [0,3,4,6]
Water trapped: 2

Why: Equal height bars can form boundaries

Step 11: Index 7 (height 3) taller than top of stack (height 1 at index 6), pop index 6

Stack after pop: [0,3,4]
Distance = 7 - 4 - 1 = 2
Bounded height = min(height[4], height[7]) - height[6] = min(1,3)-1=0
No water trapped

Why: No water trapped because bounded height is zero

Step 12: Index 7 (height 3) taller than top of stack (height 1 at index 4), pop index 4

Stack after pop: [0,3]
Distance = 7 - 3 - 1 = 3
Bounded height = min(height[3], height[7]) - height[4] = min(2,3)-1=1
Water trapped += 3*1=3 (total 5)

Why: Water trapped in bigger valley between indices 3 and 7

Step 13: Index 7 (height 3) taller than top of stack (height 2 at index 3), pop index 3

Stack after pop: [0]
Distance = 7 - 0 - 1 = 6
Bounded height = min(height[0], height[7]) - height[3] = min(0,3)-2 = -2 (no water)

Why: No water trapped because left boundary is lower

Step 14: Push index 7 (height 3) onto stack

Stack: [0,7]
Water trapped: 5

Why: New tall bar becomes boundary

Step 15: Index 8 (height 2) lower, push onto stack

Stack: [0,7,8]
Water trapped: 5

Why: Lower bar might trap water later

Step 16: Index 9 (height 1) lower, push onto stack

Stack: [0,7,8,9]
Water trapped: 5

Why: Keep track of valley bottom

Step 17: Index 10 (height 2) taller than top of stack (height 1 at index 9), pop index 9

Stack after pop: [0,7,8]
Distance = 10 - 8 - 1 = 1
Bounded height = min(height[8], height[10]) - height[9] = min(2,2)-1=1
Water trapped += 1*1=1 (total 6)

Why: Water trapped in small valley between indices 8 and 10

Step 18: Index 10 (height 2) not taller than top of stack (height 2 at index 8), push index 10

Stack: [0,7,8,10]
Water trapped: 6

Why: Equal height bars can form boundaries

Step 19: Index 11 (height 1) lower, push onto stack

Stack: [0,7,8,10,11]
Water trapped: 6

Why: Lower bar might trap water later

Result:

Final trapped water = 6 units

Annotated Code

DSA Typescript

class Stack {
  private items: number[] = [];
  push(element: number) {
    this.items.push(element);
  }
  pop(): number | undefined {
    return this.items.pop();
  }
  peek(): number | undefined {
    return this.items[this.items.length - 1];
  }
  isEmpty(): boolean {
    return this.items.length === 0;
  }
}

function trapRainWater(height: number[]): number {
  const stack = new Stack();
  let waterTrapped = 0;
  for (let i = 0; i < height.length; i++) {
    // While current bar is taller than bar at stack top
    while (!stack.isEmpty() && height[i] > height[stack.peek()!]) {
      const top = stack.pop()!; // valley bottom index
      if (stack.isEmpty()) {
        break; // no left boundary
      }
      const distance = i - stack.peek()! - 1; // width between boundaries
      const boundedHeight = Math.min(height[i], height[stack.peek()!]) - height[top];
      waterTrapped += distance * boundedHeight; // add trapped water
    }
    stack.push(i); // push current bar index
  }
  return waterTrapped;
}

// Driver code
const height = [0,1,0,2,1,0,1,3,2,1,2,1];
console.log(trapRainWater(height));

while (!stack.isEmpty() && height[i] > height[stack.peek()!]) {

Check if current bar is taller than top of stack to find right boundary

const top = stack.pop()!;

Pop valley bottom index to calculate trapped water

if (stack.isEmpty()) { break; }

Stop if no left boundary exists

const distance = i - stack.peek()! - 1;

Calculate width between left and right boundaries

const boundedHeight = Math.min(height[i], height[stack.peek()!]) - height[top];

Calculate height of trapped water bounded by left and right bars

waterTrapped += distance * boundedHeight;

Add trapped water volume for this valley

stack.push(i);

Push current bar index as potential boundary

Output

6

Complexity Analysis

Time: O(n) because each bar is pushed and popped at most once from the stack

Space: O(n) for the stack that stores indices of bars

vs Alternative: Compared to brute force O(n^2) checking left and right max for each bar, stack approach is much faster

Edge Cases

Empty height array

Returns 0 as no bars exist to trap water

DSA Typescript

for (let i = 0; i < height.length; i++) {

All bars of same height

No water trapped, returns 0

DSA Typescript

while (!stack.isEmpty() && height[i] > height[stack.peek()!]) {

Strictly increasing or decreasing bars

No trapped water, returns 0

DSA Typescript

while (!stack.isEmpty() && height[i] > height[stack.peek()!]) {

When to Use This Pattern

When you need to find trapped water between bars or heights, and want to avoid checking all pairs, use a stack to track boundaries efficiently.

Common Mistakes

Mistake: Not checking if stack is empty before accessing top, causing errors
Fix: Always check stack.isEmpty() before peek or pop operations

Mistake: Calculating distance or bounded height incorrectly by off-by-one errors
Fix: Use distance = current index - stack top index - 1 and bounded height as min of boundaries minus valley height

Summary

Calculates how much rain water can be trapped between bars using a stack to find boundaries.

Use when you want an efficient O(n) solution to the trapping rain water problem.

The stack helps find left and right boundaries to calculate trapped water in valleys.

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