Trapping Rain Water Using Stack in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trapping Rain Water Calculation

What is the output of the following JavaScript code that calculates trapped rain water using a stack?

DSA Javascript

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

console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]));

A 6

B 5

C 7

D 8

💡 Hint

Think about how the stack helps find boundaries to trap water between bars.

The code uses a stack to find the left and right boundaries for trapped water. It calculates the trapped water between bars by popping the stack and measuring the distance and height difference. For the input, the total trapped water is 6 units.

🧠 Conceptual

intermediate

Understanding Stack Usage in Trapping Rain Water

Why is a stack used in the trapping rain water problem instead of a simple loop?

A To reverse the height array for easier calculation

B To keep track of bars that can form boundaries for trapped water efficiently

C To store the total water trapped at each index

D To sort the bars in ascending order

💡 Hint

Think about how the stack helps find the left boundary for water trapping.

The stack stores indices of bars that are potential boundaries. When a higher bar is found, it helps calculate trapped water between the current bar and the previous boundary efficiently.

❓ Predict Output

advanced

Output of Modified Trapping Rain Water Code

What is the output of this modified JavaScript code that calculates trapped rain water using a stack?

DSA Javascript

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

console.log(trap([4,2,0,3,2,5]));

A 9

B 10

C 8

D 7

💡 Hint

Check how the condition height[i] >= height[stack top] affects the calculation.

The code calculates trapped water as 9 units for the input. The '>=' condition allows popping bars of equal height, correctly calculating trapped water.

🔧 Debug

advanced

Identify the Error in Trapping Rain Water Code

What error will this JavaScript code produce when calculating trapped rain water?

DSA Javascript

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

console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]));

A ReferenceError: stack is not defined

B SyntaxError: Unexpected token

C No error, outputs 0

D TypeError: Cannot read property of undefined

💡 Hint

Check the stack index used inside the while condition.

The code uses stack[stack.length] which is undefined (index out of range). height[undefined] is undefined, so height[i] > undefined is always false. The while loop never executes its body, the stack never pops, water remains 0, and no runtime error occurs.

🧠 Conceptual

expert

Why Does the Stack-Based Algorithm Work for Trapping Rain Water?

Which explanation best describes why the stack-based algorithm correctly calculates trapped rain water?

A It calculates trapped water by summing the difference between max height and each bar height directly

B It sorts the bars and calculates water by comparing adjacent bars only

C It uses recursion to divide the problem into smaller subproblems of trapped water

D It uses the stack to find the nearest taller bars on both sides to calculate trapped water between them

💡 Hint

Think about how the stack helps identify boundaries for water trapping.

The stack stores indices of bars that form boundaries. When a higher bar is found, it calculates trapped water between the current bar and the previous taller bar on the stack, ensuring correct water volume calculation.

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