Trapping Rain Water Using Stack in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a stack to solve the Trapping Rain Water problem?

Use a stack to keep track of bars that are bounded by higher bars on both sides. When a higher bar is found, calculate trapped water with the bars in the stack.

beginner

In the stack approach, what does each element in the stack represent?

Each element represents the index of a bar in the elevation map, stored in increasing order of height.

intermediate

Why do we pop from the stack when the current bar height is greater than the top of the stack?

Because we found a right boundary taller than the bar at the top, so we can calculate trapped water between the left boundary (new top) and right boundary (current bar).

intermediate

How is the width of trapped water calculated in the stack method?

Width = current index - index of new top of stack - 1, representing the horizontal distance between boundaries.

beginner

What is the time complexity of the Trapping Rain Water problem using the stack approach?

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

What does the stack store in the Trapping Rain Water problem?

A Widths between bars

B Indices of bars

C Water trapped at each bar

D Heights of bars

The stack stores indices of bars to help calculate trapped water using their positions.

When do we calculate trapped water in the stack approach?

A When current bar is taller than top of stack

B At the end of the array only

C When current bar is shorter than top of stack

D Before pushing any bar

We calculate trapped water when the current bar is taller than the top of the stack, indicating a right boundary.

What is the role of the 'left boundary' in the stack method?

A It is the new top of the stack after popping

B It is the bar at the bottom of the stack

C It is the current bar

D It is the tallest bar in the array

The left boundary is the new top of the stack after popping the middle bar, used to calculate trapped water width.

What happens if the stack is empty after popping a bar during calculation?

A We continue calculating trapped water

B We push the popped bar back

C We stop because no left boundary exists

D We reset the stack

If the stack is empty, there is no left boundary to trap water, so calculation stops for that bar.

What is the space complexity of the stack approach for Trapping Rain Water?

A O(n^2)

B O(1)

C O(log n)

D O(n)

The stack can hold up to n indices in the worst case, so space complexity is O(n).

Explain step-by-step how the stack is used to calculate trapped rain water.

Think about how boundaries form a container for water.

Describe how trapped water volume is calculated between bars using the stack method.

Focus on how height and width define the water area.

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