Trapping Rain Water Using Stack in DSA Javascript - 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

↓

Add trapped water to total

↓

Push current index to stack

↓

Repeat until end

↓

Return total trapped water

We use a stack to keep indices of bars. When current bar is higher than top of stack, we pop and calculate trapped water between bars.

Execution Sample

DSA Javascript

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

Calculates total trapped rain water using a stack to track bars and compute 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	Stack: [0] (height 0)
2	Push index 1	1	[0,1]	-	-	-	0	0	Stack: [0,1] (heights 0,1)
3	Push index 2	2	[0,1,2]	-	-	-	0	0	Stack: [0,1,2] (heights 0,1,0)
4	Pop index 2	3	[0,1]	2	1	1	1	1	Water trapped between indices 1 and 3 over 1 unit width
5	Pop index 1	3	[0]	1	2	0	0	1	No water added, bounded height zero
6	Push index 3	3	[0,3]	-	-	-	0	1	Stack: [0,3] (heights 0,2)
7	Push index 4	4	[0,3,4]	-	-	-	0	1	Stack: [0,3,4] (heights 0,2,1)
8	Pop index 4	5	[0,3]	4	1	1	1	2	Water trapped between indices 3 and 5 over 1 unit width
9	Pop index 3	5	[0]	3	3	0	0	2	No water added, bounded height zero
10	Push index 5	5	[0,5]	-	-	-	0	2	Stack: [0,5] (heights 0,2)
11	Push index 6	6	[0,5,6]	-	-	-	0	2	Stack: [0,5,6] (heights 0,2,1)
12	Pop index 6	7	[0,5]	6	1	1	1	3	Water trapped between indices 5 and 7 over 1 unit width
13	Pop index 5	7	[0]	5	5	0	0	3	No water added, bounded height zero
14	Push index 7	7	[0,7]	-	-	-	0	3	Stack: [0,7] (heights 0,3)
15	End of array	-	[0,7]	-	-	-	0	3	Total trapped water = 3 units

💡 Reached end of height array, total trapped water calculated.

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 8	After Step 12	After Step 15
stack	[]	[0]	[0,1]	[0,3]	[0,5]	[0,7]
water	0	0	1	2	3	3
i	-	0	3	5	7	-

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 calculated when we find a right boundary taller than the bar at stack top. See execution_table rows 4 and 8 where popping happens only when height[i] > height[stack top].

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

If stack is empty after popping, it means no left boundary exists to trap water. So we break to avoid invalid calculations. This is shown in execution_table rows 5 and 9.

How is the distance between bars calculated for trapped water?

Distance is the horizontal gap between current index and new stack top minus one. This is shown in execution_table rows 4, 8, and 12 under 'Distance' column.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the water added and why?

A 1 unit, because distance is 1 and bounded height is 1

B 0 units, because bounded height is zero

C 2 units, because distance is 2 and bounded height is 1

D 3 units, because distance is 3 and bounded height is 1

💡 Hint

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

At which step does the total trapped water reach 3 units?

A Step 8

B Step 12

C Step 15

D Step 4

💡 Hint

Look at 'Total Water' column in execution_table for final value.

If the height at index 3 was lower, how would the stack change at step 6?

A Stack would push index 3 without popping

B Stack would pop index 1 before pushing index 3

C Stack would be empty at step 6

D Stack would pop index 0 before pushing index 3

💡 Hint

Refer to condition for popping in execution_table rows 4 and 6.

Concept Snapshot

Trapping Rain Water Using Stack:
- Use stack to store indices of bars
- Iterate over heights
- While current height > height at stack top:
  - Pop top, calculate trapped water using distance and bounded height
- Push current index
- Sum trapped water and return total

Full Transcript

This visualization shows how to calculate trapped rain water using a stack. We keep indices of bars in a stack. When we find a bar taller than the top of the stack, we pop from the stack and calculate trapped water between the current bar and the new top of the stack. We track distance and bounded height to find trapped water volume. We repeat until all bars are processed and return the total trapped water. The execution table shows each step, stack changes, water added, and total water accumulated. Key moments clarify why popping happens only when current height is greater, why we check for empty stack, and how distance is calculated. The quiz tests understanding of these steps.

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