Trapping Rain Water Using Stack in DSA Typescript - Deep Dive

Overview - Trapping Rain Water Using Stack

What is it?

Trapping Rain Water Using Stack is a method to find how much water can be trapped between bars of different heights after it rains. Imagine bars of different heights placed side by side, and water fills the gaps between them. The stack helps keep track of bars to calculate trapped water efficiently by remembering where the walls are.

Why it matters

Without this method, calculating trapped water would be slow and complicated, especially for large sets of bars. This algorithm solves the problem quickly and uses less memory, making it useful in real-world situations like designing drainage systems or analyzing landscapes. Without it, engineers and programmers would struggle with inefficient solutions that waste time and resources.

Where it fits

Before learning this, you should understand arrays, basic loops, and stacks as a data structure. After mastering this, you can explore other water trapping methods like two-pointer techniques and dynamic programming, and then move on to more complex stack problems or interval-based algorithms.

Mental Model

Core Idea

Use a stack to remember bars that might trap water, and calculate trapped water when a taller bar forms a boundary on the right.

Think of it like...

Imagine a row of buildings with different heights and rainwater filling the spaces between them. The stack is like a list of buildings waiting to see if a taller building comes along to hold water between them.

Heights: 0 1 0 2 1 0 1 3 2 1 2 1
Stack process:
  ┌─────────────┐
  │ Index stack │
  ├─────────────┤
  │             │
  │             │
  └─────────────┘
Water trapped when current bar > top of stack bar

Example:
Index: 0 1 2 3
Height:0 1 0 2
Stack: push 0, pop 0 & push 1, push 2, pop 2 when 3 comes, calculate water between 1 and 3

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

Concept: Introduce the problem of trapping rain water between bars of different heights.

Imagine bars placed side by side with varying heights. When it rains, water fills the gaps between taller bars. The goal is to find the total amount of water trapped. For example, bars with heights [0,1,0,2] trap 1 unit of water between bars 1 and 3.

Result

You understand the problem visually and conceptually: water is trapped where shorter bars are between taller bars.

Understanding the physical setup helps you visualize why water can be trapped and where to look for it.

2

Foundation

Basics of Stack Data Structure

Concept: Learn what a stack is and how it works with push and pop operations.

A stack is like a pile of plates: you add (push) plates on top and remove (pop) from the top. It follows Last-In-First-Out (LIFO) order. We will use a stack to remember bars that might trap water.

Result

You can use a stack to keep track of bars and their indices while scanning the array.

Knowing how a stack works is essential because it helps manage bars waiting to form boundaries for trapped water.

3

Intermediate

Using Stack to Track Bars for Water Trapping

🤔Before reading on: do you think the stack should store bar heights or their indices? Commit to your answer.

Concept: Store indices of bars in the stack to calculate distances and heights for trapped water.

We scan bars from left to right. For each bar: - While the current bar is taller than the bar at the top of the stack, pop the top. - Calculate trapped water using the popped bar as the bottom, current bar as right boundary, and new top of stack as left boundary. - Push current bar index onto the stack. This way, the stack keeps bars that are not yet bounded on the right.

Result

The stack helps find trapped water by identifying boundaries and the width between them.

Storing indices instead of heights allows calculation of width between bars, which is crucial for water volume.

4

Intermediate

Calculating Water Volume Between Bars

🤔Before reading on: do you think trapped water depends on the shorter or taller boundary bar? Commit to your answer.

Concept: Water trapped depends on the shorter boundary bar minus the height of the bottom bar, multiplied by the width between boundaries.

When popping a bar from the stack, the water trapped is: - Height = min(left boundary height, right boundary height) - popped bar height - Width = distance between left and right boundaries - 1 Multiply height and width to get trapped water volume for that section.

Result

You can calculate trapped water for each bounded section accurately.

Knowing that water level is limited by the shorter boundary prevents overestimating trapped water.

5

Intermediate

Implementing the Stack-Based Algorithm in TypeScript

🤔Before reading on: do you think the algorithm runs in linear or quadratic time? Commit to your answer.

Concept: Write code that uses a stack to calculate total trapped water in one pass through the array.

TypeScript code: 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 boundedHeight = Math.min(height[i], height[stack[stack.length - 1]]) - height[top]; water += distance * boundedHeight; } stack.push(i); } return water; } Example: trap([0,1,0,2,1,0,1,3,2,1,2,1]) returns 6.

Result

The function returns the total trapped water amount efficiently in O(n) time.

Implementing the algorithm solidifies understanding and shows how stack operations solve the problem efficiently.

6

Advanced

Why Stack Approach is Efficient and Correct

🤔Before reading on: do you think the stack approach uses extra space proportional to input size? Commit to your answer.

Concept: The stack approach processes each bar once, using extra space only for indices of bars that might trap water.

Each bar is pushed and popped at most once, so time complexity is O(n). The stack size is at most the number of bars, so space complexity is O(n). This approach avoids nested loops and repeated calculations, unlike naive methods.

Result

You understand the algorithm's efficiency and why it is preferred for large inputs.

Knowing the algorithm's time and space behavior helps choose it wisely in performance-critical situations.

7

Expert

Handling Edge Cases and Stack Behavior Surprises

🤔Before reading on: do you think the algorithm handles flat bars (equal heights) correctly? Commit to your answer.

Concept: Explore how the stack algorithm deals with bars of equal height and empty stack conditions.

When bars have equal height, the algorithm treats them as boundaries without trapping water between them. The stack may pop multiple bars if the current bar is taller, ensuring all trapped water is counted. If the stack becomes empty after popping, no left boundary exists, so no water is trapped for that section.

Result

The algorithm correctly handles tricky cases like flat bars and avoids errors from empty stacks.

Understanding these edge cases prevents bugs and ensures robustness in real-world data.

Under the Hood

The stack stores indices of bars in increasing height order. When a taller bar arrives, it signals a right boundary. The algorithm pops bars lower than the current bar, calculating trapped water between the current bar (right boundary) and the new top of the stack (left boundary). This process repeats until the stack is empty or the current bar is not taller than the top. This ensures each trapped water section is counted exactly once.

Why designed this way?

This design avoids nested loops by using a stack to remember potential boundaries. Earlier methods used double loops causing slow performance. The stack approach balances time and space efficiency by processing each bar once and using the stack to track boundaries dynamically.

Input heights: [0,1,0,2]

Index: 0 1 2 3
Height:0 1 0 2

Stack operations:
Start: stack=[]
Push 0 -> stack=[0]
pop 0 push 1 -> stack=[1]
Current bar 0 < top bar 1, push 2 -> stack=[1,2]
Current bar 2 > top bar 0 (index 2), pop 2
Calculate water trapped between bars at indices 1 and 3
then 2 > 1 pop 1 (empty, no calc)
Push 3 -> stack=[3]

Flow:
┌─────────────┐
│ Stack       │
│ [0]         │
│ [1]         │
│ [1,2]       │
│ [1]         │
│ [3]         │
└─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does the stack store bar heights or indices? Commit to your answer.

Common Belief: The stack stores the heights of bars to calculate trapped water.

Reality: The stack stores indices of bars, not their heights, to calculate distances and heights correctly.

Why it matters: Storing heights instead of indices makes it impossible to calculate the width between bars, leading to incorrect water volume.

Quick: Does trapped water depend on the taller or shorter boundary? Commit to your answer.

Common Belief: Trapped water depends on the taller boundary bar height.

Reality: Trapped water depends on the shorter boundary bar height minus the bottom bar height.

Why it matters: Using the taller boundary causes overestimation of trapped water, resulting in wrong answers.

Quick: Does the algorithm run in O(n) or O(n^2) time? Commit to your answer.

Common Belief: The stack-based algorithm runs in quadratic time because of nested loops.

Reality: The algorithm runs in linear time O(n) because each bar is pushed and popped at most once.

Why it matters: Misunderstanding time complexity may lead to rejecting this efficient method for large inputs.

Quick: Does the algorithm trap water between bars of equal height? Commit to your answer.

Common Belief: Water is trapped between bars of equal height if there is space.

Reality: No water is trapped between bars of equal height because water level equals bar height.

Why it matters: Assuming water traps between equal bars causes incorrect calculations and bugs.

Expert Zone

1

The stack only stores indices of bars that form a non-increasing sequence of heights, ensuring efficient boundary detection.

2

When multiple bars of the same height appear, the algorithm treats them as a single boundary to avoid double counting trapped water.

3

The algorithm's correctness depends on carefully handling empty stack conditions to avoid runtime errors and incorrect water calculations.

When NOT to use

This stack approach is less intuitive for beginners and uses extra space proportional to input size. For very large inputs with memory constraints, the two-pointer approach is preferred as it uses constant space. Also, if you need to find trapped water with dynamic updates to bar heights, segment trees or binary indexed trees might be better.

Production Patterns

In real systems, this algorithm is used in terrain analysis, flood simulation, and drainage design software. It is often combined with visualization tools to show trapped water areas. In coding interviews, it tests understanding of stacks and problem-solving skills under time pressure.

Connections

Two-Pointer Technique

Alternative algorithm to solve the same problem using two pointers from both ends.

Understanding the stack method helps appreciate the two-pointer approach's space efficiency and vice versa.

Histogram Largest Rectangle Problem

Both use stacks to process bar heights and indices for area or volume calculations.

Recognizing the stack pattern in both problems reveals a common strategy for handling bar-based computations.

Civil Engineering Drainage Systems

The algorithm models how water accumulates between barriers, similar to real drainage design.

Knowing this algorithm aids in understanding and simulating water flow and retention in physical landscapes.

Common Pitfalls

#1 Storing bar heights in the stack instead of indices.

Wrong approach:

let stack: number[] = [];
for (let i = 0; i < height.length; i++) {
while (stack.length > 0 && height[i] > stack[stack.length - 1]) {
let top = stack.pop()!;
// Incorrect: top is height, not index
// Cannot calculate distance
}
stack.push(height[i]);
}

Correct approach:

let stack: number[] = [];
for (let i = 0; i < height.length; i++) {
while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
let top = stack.pop()!;
// top is index, can calculate distance
}
stack.push(i);
}

Root cause:

Confusing what the stack should store leads to inability to calculate width between bars.

#2 Calculating trapped water using the taller boundary height instead of the shorter one.

Wrong approach:

let boundedHeight = Math.max(height[i], height[stack[stack.length - 1]]) - height[top];

Correct approach:

let boundedHeight = Math.min(height[i], height[stack[stack.length - 1]]) - height[top];

Root cause:

Misunderstanding that water level is limited by the shorter boundary causes overestimation.

#3 Not checking if the stack is empty before calculating trapped water.

Wrong approach:

while (height[i] > height[stack[stack.length - 1]]) {
let top = stack.pop()!;
// No check if stack is empty
let distance = i - stack[stack.length - 1] - 1;
// May cause error if stack empty
}

Correct approach:

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;
}

Root cause:

Ignoring empty stack leads to runtime errors and incorrect calculations.

Key Takeaways

Trapping rain water using a stack efficiently finds water trapped between bars by remembering potential boundaries.

The stack stores indices, not heights, to calculate distances and water volumes correctly.

Water trapped depends on the shorter boundary height minus the bottom bar height, multiplied by the width between boundaries.

Each bar is pushed and popped at most once, making the algorithm run in linear time with extra space for the stack.

Handling edge cases like equal height bars and empty stack conditions is crucial for correctness and robustness.

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