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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trapping Rain Water Calculation

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

DSA C++

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int trap(vector<int>& height) {
    int n = height.size();
    stack<int> st;
    int water = 0;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && height[i] > height[st.top()]) {
            int top = st.top();
            st.pop();
            if (st.empty()) break;
            int distance = i - st.top() - 1;
            int bounded_height = min(height[i], height[st.top()]) - height[top];
            water += distance * bounded_height;
        }
        st.push(i);
    }
    return water;
}

int main() {
    vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << trap(height) << endl;
    return 0;
}

A 8

B 6

C 7

D 5

💡 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 water trapped between bars by considering the distance and bounded height. For the given input, the total trapped water is 6 units.

🧠 Conceptual

intermediate

Understanding Stack Usage in Trapping Rain Water

Why does the stack help in solving the trapping rain water problem efficiently?

A It stores the height values to calculate total water directly.

B It sorts the bars in ascending order to calculate water.

C It keeps track of indices of bars to find boundaries for trapped water.

D It reverses the array to simplify calculations.

💡 Hint

Think about how boundaries are found between bars.

The stack stores indices of bars in a way that helps find left and right boundaries for water trapping. When a higher bar is found, it calculates trapped water between the current bar and the bar at the stack's top.

🔧 Debug

advanced

Identify the Error in Trapping Rain Water Code

What error will the following code produce when run?

DSA C++

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int trap(vector<int>& height) {
    int n = height.size();
    stack<int> st;
    int water = 0;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && height[i] > height[st.top()]) {
            int top = st.top();
            st.pop();
            if (st.empty()) break;
            int distance = i - st.top() - 1;
            int bounded_height = min(height[i], height[st.top()]) - height[top];
            water += distance * bounded_height;
        }
        st.push(i);
    }
    return water;
}

int main() {
    vector<int> height = {4,2,0,3,2,5};
    cout << trap(height) << endl;
    return 0;
}

A Compilation error due to missing semicolon

B Output: 7

C Output: 9

D Runtime error: out_of_range exception

💡 Hint

Check the loop boundary condition carefully.

The original code had 'for (int i = 0; i <= n; i++)' which accesses height[n], causing out_of_range runtime error. It should be 'for (int i = 0; i < n; i++)'.

❓ Predict Output

advanced

Output of Modified Trapping Rain Water Code

What is the output of this modified C++ code snippet?

DSA C++

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int trap(vector<int>& height) {
    int n = height.size();
    stack<int> st;
    int water = 0;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && height[i] >= height[st.top()]) {
            int top = st.top();
            st.pop();
            if (st.empty()) break;
            int distance = i - st.top() - 1;
            int bounded_height = min(height[i], height[st.top()]) - height[top];
            water += distance * bounded_height;
        }
        st.push(i);
    }
    return water;
}

int main() {
    vector<int> height = {4,2,0,3,2,5};
    cout << trap(height) << endl;
    return 0;
}

A 9

B 7

C 8

D 10

💡 Hint

Note the use of '>=' in the while condition instead of '>'.

Using '>=' allows popping bars of equal height, but the trapped water calculation remains the same for this input, resulting in 9 units of water.

🚀 Application

expert

Maximum Water Trapped in a Large Histogram

Given a histogram with heights: [5,2,1,2,1,5,3,2,4,1,2,3,1,2,1], what is the maximum amount of water trapped using the stack method?

A 28

B 27

C 26

D 25

💡 Hint

Visualize the bars and calculate trapped water between boundaries using the stack approach.

The stack method calculates trapped water by finding boundaries and summing trapped units. For this input, the total trapped water is 28 units.

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

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 order of the bars

Solution

1. Step 1: Understand the role of the stack

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

2. Step 2: Explain why other options are incorrect

   The stack does not store water amount or sort bars; it helps track bars for water calculation.

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 = A [OK]

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

Common Mistakes:

• Thinking stack stores water amount
• Assuming stack sorts bars
• Confusing stack with array for heights

2. Which of the following C++ code snippets correctly declares a stack to be used for trapping rain water indices?

easy

A. std::stack<int> st;

B. stack<int> st = new stack<int>();

C. std::stack st<int>;

D. stack<int> st();

Solution

1. Step 1: Check correct C++ stack declaration syntax

   Correct syntax is std::stack<int> st; to declare a stack of integers.

2. Step 2: Identify errors in other options

   stack<int> st = new stack<int>(); uses incorrect syntax with 'new'; C has wrong template placement; D declares a function, not a stack.

3. Final Answer:

   std::stack<int> st; -> Option A

4. Quick Check:

   Correct stack declaration = B [OK]

Hint: Use std::stack<int> st; to declare stack [OK]

Common Mistakes:

• Using 'new' keyword incorrectly
• Wrong template syntax
• Declaring function instead of stack

3. What is the output of the following C++ code snippet that uses stack to calculate trapped rain water?

int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
int n = 12;
std::stack<int> st;
int water = 0;
for (int i = 0; i < n; i++) {
  while (!st.empty() && height[i] > height[st.top()]) {
    int top = st.top();
    st.pop();
    if (st.empty()) break;
    int distance = i - st.top() - 1;
    int bounded_height = std::min(height[i], height[st.top()]) - height[top];
    water += distance * bounded_height;
  }
  st.push(i);
}
std::cout << water << std::endl;

medium

A. 8

B. 5

C. 6

D. 7

Solution

1. Step 1: Trace the stack operations and water calculation

   The code calculates trapped water for the given heights array using stack logic. The total trapped water is 6 units.

2. Step 2: Verify calculations with known example

   This is a classic example where trapped water is 6 units, matching the output of the code.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Trapped water = 6 [OK]

Hint: Classic example traps 6 units water [OK]

Common Mistakes:

• Miscounting distance between bars
• Wrong bounded height calculation
• Ignoring empty stack break condition

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

std::stack<int> st;
int water = 0;
for (int i = 0; i < height.size(); i++) {
  while (!st.empty() && height[i] >= height[st.top()]) {
    int top = st.top();
    st.pop();
    if (st.empty()) break;
    int distance = i - st.top() - 1;
    int bounded_height = std::min(height[i], height[st.top()]) - height[top];
    water += distance * bounded_height;
  }
  st.push(i);
}
std::cout << water << std::endl;

medium

A. No break condition inside while loop

B. Missing initialization of water variable

C. Stack should store heights, not indices

D. Using >= instead of > in while condition causes incorrect water calculation

Solution

1. Step 1: Analyze the while loop condition

   The condition uses >= which causes popping bars of equal height, leading to incorrect trapped water calculation.

2. Step 2: Explain correct condition and impact

   Using > ensures only bars lower than current are popped, preserving correct boundaries for water trapping.

3. Final Answer:

   Using >= instead of > in while condition causes incorrect water calculation -> Option D

4. Quick Check:

   Use > not >= in while condition [OK]

Hint: Use > not >= in while condition [OK]

Common Mistakes:

• Using >= instead of > in while condition
• Storing heights instead of indices in stack
• Forgetting break when stack is empty

5. Given the heights array {4, 2, 0, 3, 2, 5}, what is the total trapped rain water calculated using the stack approach?

hard

A. 8

B. 7

C. 9

D. 6

Solution

1. Step 1: Calculate trapped water between bars using stack logic

   Between bars, trapped water units are: 2 units between 4 and 3, 1 unit between 3 and 5, and 5 units between 2 and 5, totaling 8 units.

2. Step 2: Sum trapped water units

   Sum of trapped water is 8 units for the given array.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   Trapped water total = 8 [OK]

Hint: Sum water trapped between boundaries carefully [OK]

Common Mistakes:

• Ignoring zero height bars
• Miscounting trapped water between bars
• Not considering both left and right boundaries