Trapping Rain Water Using Stack in DSA Javascript

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.

Analogy: Imagine a row of walls with different heights. When rain falls, water collects in dips between taller walls. The stack is like a helper that remembers where dips start until a taller wall closes the dip.

Height bars: 0 1 0 2 1 0 1 3 2 1 2 1
Stack: empty initially
Water trapped: 0

Visual:
|       |
|   |   |   |
|_|_|_|_|_|_|_
Indexes: 0 1 2 3 4 5 6 7 8 9 10 11

Dry Run Walkthrough

Input: height = [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 index to compare with next bars

Step 2: i=1 height[1]=1 > height[0]=0, pop index 0, stack empty - no water calculation, push index 1

stack: [1]
water trapped: 0

Why: Pop smaller bar, no left boundary so no trapped water, push current as new boundary

Step 3: Push index 2 (height 0) since 0 < height[1]=1

stack: [1,2]
water trapped: 0

Why: Lower bar, possible bottom of a dip

Step 4: i=3 height 2 > height[2]=0, pop index 2

stack after pop: [1]
Calculate: distance=3-1-1=1, bounded height=min(2,1)-0=1, water +=1
Total water: 1

Why: Found dip: bar1(1) and bar3(2) trap 1 unit above bar2(0)

Step 5: Still at i=3, height 2 > height[1]=1, pop index 1, stack now empty - break no calculation

stack: []
Total water: 1

Why: No left boundary for popped bar1, so no additional water

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

stack: [3]
Total water: 1

Why: Current bar becomes new potential boundary

Step 7: Push index 4 (height 1) < height[3]=2

stack: [3,4]
Total water: 1

Why: Lower bar, possible dip bottom

Step 8: Push index 5 (height 0) < height[4]=1

stack: [3,4,5]
Total water: 1

Why: Even lower, extends dip

Step 9: i=6 height 1 > height[5]=0, pop 5

stack: [3,4]
distance=6-4-1=1, bh=min(1,1)-0=1, water+=1 Total:2

Why: Trap 1 unit between bar4(1) and bar6(1) above bar5(0)

Step 10: At i=6 height1 == height[4]=1, no pop, push 6

stack: [3,4,6]
Total:2

Why: Equal height, push as potential boundary

Step 11: i=7 height3 > height[6]=1, pop 6

stack: [3,4]
dist=7-4-1=2, bh=min(3,1)-1=0, no water added Total:2

Why: Plateau between 4 and6 at height1, no trap

Step 12: Still i=7 3 > height[4]=1, pop 4

stack: [3]
dist=7-3-1=3, bh=min(3,2)-1=1, water+=3 Total:5

Why: Trap 1 height over 3 width between bar3(2) and bar7(3)

Step 13: Still i=7 3 > height[3]=2, pop 3, stack empty break no calc

stack: []
Total:5

Why: No left boundary for bar3

Step 14: Push current index 7 onto stack

stack: [7]
Total water: 5

Why: Set new boundary for future trapping

Step 15: Push index 8 (height 2) onto stack since height[8] < height[7]

stack: [7,8]
Total water: 5

Why: Lower bar, possible dip bottom

Step 16: Push index 9 (height 1) onto stack since height[9] < height[8]

stack: [7,8,9]
Total water: 5

Why: Lower bar, possible dip bottom

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

stack after pop: [7,8]
Calculate trapped water:
Distance = 10 - 8 - 1 = 1
Bounded height = min(height[10], height[8]) - height[9] = min(2,2)-1=1
Water trapped += 1*1=1
Total water: 6

Why: Found dip bounded by bars at index 8 and 10 trapping 1 unit water

Step 18: Current bar height 2 equals height at top of stack (height 2 at index 8), push index 10

stack: [7,8,10]
Total water: 6

Why: Push to keep track of current bar

Step 19: Push index 11 (height 1) onto stack since height[11] < height[10]

stack: [7,8,10,11]
Total water: 6

Why: Lower bar, possible dip bottom

Result:

Final trapped water: 6 units

Annotated Code

DSA Javascript

class Stack {
  constructor() {
    this.items = [];
  }
  push(element) {
    this.items.push(element);
  }
  pop() {
    return this.items.pop();
  }
  top() {
    return this.items[this.items.length - 1];
  }
  isEmpty() {
    return this.items.length === 0;
  }
}

function trap(height) {
  const stack = new Stack();
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    // While current bar is taller than top of stack bar
    while (!stack.isEmpty() && height[i] > height[stack.top()]) {
      const top = stack.pop(); // Pop the bottom of the dip
      if (stack.isEmpty()) {
        break; // No left boundary
      }
      const distance = i - stack.top() - 1; // Width between boundaries
      const boundedHeight = Math.min(height[i], height[stack.top()]) - height[top];
      water += distance * boundedHeight; // Add trapped water
    }
    stack.push(i); // Push current bar index
  }
  return water;
}

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

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

Check if current bar can trap water by being taller than previous bars

const top = stack.pop();

Pop the bottom bar of the dip to calculate trapped water

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

Stop if no left boundary to trap water

const distance = i - stack.top() - 1;

Calculate width between left and right boundaries

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

Calculate height of trapped water bounded by shorter boundary

water += distance * boundedHeight;

Add trapped water volume for this dip

stack.push(i);

Push current bar index as new boundary or dip bottom

Output

6

Complexity Analysis

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

Space: O(n) because the stack can hold all bar indices in worst case

vs Alternative: Compared to two-pointer approach which also runs in O(n) time but uses O(1) space, stack method is easier to understand for some but uses extra space

Edge Cases

Empty height array

Returns 0 as no bars to trap water

DSA Javascript

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

All bars same height

Returns 0 as no dips to trap water

DSA Javascript

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

Strictly increasing heights

Returns 0 as no dips formed

DSA Javascript

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

When to Use This Pattern

When you see a problem asking how much water can be trapped between bars or heights, reach for the stack pattern because it helps find boundaries efficiently.

Common Mistakes

Mistake: Not checking if stack is empty before accessing top, causing errors
Fix: Add condition to break loop if stack becomes empty after popping

Mistake: Calculating distance or bounded height incorrectly by off-by-one errors
Fix: Use 'distance = current_index - stack.top() - 1' and bounded height as min of boundaries minus bottom height

Summary

Calculates trapped rain water between bars using a stack to find boundaries.

Use when you need to find trapped water volume efficiently in one pass.

The stack remembers bars that form dips until a taller bar closes the dip to calculate trapped water.

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 keep track of bars that are not yet processed for water trapping

C. To sort the heights of bars in ascending order

D. To reverse the array of bar heights

Solution

1. Step 1: Understand the role of stack in the algorithm

   The stack stores indices of bars that are waiting to find a right boundary to trap water.

2. Step 2: Clarify what the stack does not do

   The stack does not store water amounts or sort bars; it helps find boundaries for trapped water.

3. Final Answer:

   To keep track of bars that are not yet processed for water trapping -> Option B

4. Quick Check:

   Stack tracks bars for trapping water [OK]

Hint: Stack holds indices of bars waiting for right boundary [OK]

Common Mistakes:

• Thinking stack stores water volume directly
• Assuming stack sorts the bars
• Believing stack reverses the array

2. Which of the following is the correct way to initialize an empty stack in JavaScript for the trapping rain water problem?

easy

A. const stack = [];

B. const stack = {};

C. const stack = null;

D. const stack = new Stack();

Solution

1. Step 1: Identify the correct data structure for stack in JavaScript

   JavaScript uses arrays as stacks by pushing and popping elements.

2. Step 2: Check each option

   const stack = []; initializes an empty array, which works as a stack. const stack = {}; is an object, not a stack. const stack = null; is null, no stack. const stack = new Stack(); assumes a Stack class which is not built-in.

3. Final Answer:

   const stack = []; -> Option A

4. Quick Check:

   Empty array for stack [OK]

Hint: Use empty array [] as stack in JavaScript [OK]

Common Mistakes:

• Using object {} instead of array
• Assuming Stack class exists by default
• Initializing stack as null

3. What will be the output of the following code snippet that uses stack to calculate trapped rain water?

const height = [0,1,0,2,1,0,1,3,2,1,2,1];
function trap(height) {
  let stack = [];
  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 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. 6

B. 5

C. 7

D. 8

Solution

1. Step 1: Understand the input and algorithm flow

   The input array represents bar heights. The stack-based algorithm calculates trapped water by finding boundaries and distances.

2. Step 2: Trace the code logic mentally

   The code correctly calculates trapped water for the given heights, which is a classic example resulting in 6 units of water trapped.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Classic trapping rain water example = 6 [OK]

Hint: Classic example height array traps 6 units water [OK]

Common Mistakes:

• Miscounting trapped water units
• Ignoring stack empty check
• Wrong distance or bounded height calculation

4. Identify the error in the following code snippet for trapping rain water using stack:

function trap(height) {
  let stack = [];
  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 boundedHeight = Math.min(height[i], height[stack[stack.length - 1]]) - height[top];
      water += distance * boundedHeight;
    }
    stack.push(i);
  }
  return water;
}

medium

A. The distance calculation is incorrect

B. The stack should be initialized as an object, not array

C. The comparison should be >, not >= in the while condition

D. The water variable should be reset inside the loop

Solution

1. Step 1: Analyze the while loop condition

   The condition uses >= which causes incorrect popping when heights are equal, leading to wrong trapped water calculation.

2. Step 2: Correct the condition

   Changing >= to > ensures only strictly higher bars trigger popping, preserving correct boundaries.

3. Final Answer:

   The comparison should be >, not >= in the while condition -> Option C

4. Quick Check:

   Use > in while condition to avoid wrong pops [OK]

Hint: Use >, not >=, to avoid popping equal height bars [OK]

Common Mistakes:

• Using >= causes incorrect water calculation
• Initializing stack as object instead of array
• Resetting water inside loop wrongly

5. Given the heights array [4, 2, 0, 3, 2, 5], what is the total trapped rain water calculated using the stack method?

hard

A. 6

B. 7

C. 8

D. 9

Solution

1. Step 1: Visualize the bars and trapped water

   Bars heights: 4,2,0,3,2,5. Water trapped between bars is calculated by stack method considering boundaries and distances.

2. Step 2: Calculate trapped water step-by-step

   Water at index 1: 2, index 2: 4, index 3: 1, index 4: 2, total 9 units.

3. Final Answer:

   9 -> Option D

4. Quick Check:

   Sum trapped water units = 9 [OK]

Hint: Sum water between boundaries carefully for correct total [OK]

Common Mistakes:

• Miscounting trapped water units
• Ignoring zero height bars
• Wrong boundary identification