Trapping Rain Water Using Stack in DSA C++

Mental Model

We use a stack to keep track of bars that can trap water between them. When we find a taller bar, we calculate trapped water with the bars in the stack.

Analogy: Imagine a row of walls of different heights holding rainwater. When a taller wall appears, water trapped between the previous shorter walls and this taller wall can be measured.

Height bars: 0 1 0 2 1 0 1 3 2 1 2 1
Stack stores indices of bars that might trap water
Example:
Index: 0 1 2 3 4 5 6 7 8 9 10 11
Height:0 1 0 2 1 0 1 3 2 1  2  1
Stack: [] initially empty

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: i=0: 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) > height[0]=0, pop index 0

Popped index 0, stack now empty

Why: Current bar taller than top of stack

Step 3: Stack empty after pop, no water calculation, push index 1

Stack: [1]
Water trapped: 0

Why: No left boundary for water trapping

Step 4: i=2 (height 0) < height[1]=1, push index 2

Stack: [1,2]
Water trapped: 0

Why: Current bar shorter, keep for possible water trapping

Step 5: i=3 (height 2) > height[2]=0, pop index 2

Popped index 2, stack now [1]

Why: Found right boundary taller than top bar

Step 6: Calculate distance = 3 - 1 - 1 = 1, bounded height = min(2,1) - 0 = 1, water += 1

Water trapped: 1

Why: Water trapped between bars at indices 1 and 3 above index 2

Step 7: Still height[3]=2 > height[1]=1, pop index 1

Popped index 1, stack now empty

Why: Continue popping while current is taller

Step 8: Stack empty, no more calculation, push index 3

Stack: [3]
Water trapped: 1

Why: Add new taller bar index for future trapping

Step 9: i=4 (height 1) < height[3]=2, push index 4

Stack: [3,4]
Water trapped: 1

Why: Keep shorter bar for possible trapping

Step 10: i=5 (height 0) < height[4]=1, push index 5

Stack: [3,4,5]
Water trapped: 1

Why: Keep shorter bar for possible trapping

Step 11: i=6 (height 1) > height[5]=0, pop index 5

Popped index 5, stack now [3,4]

Why: Found right boundary taller than top bar

Step 12: Calculate distance = 6 - 4 - 1 = 1, bounded height = min(1,1) - 0 = 1, water += 1

Water trapped: 2

Why: Water trapped between bars at indices 4 and 6 above index 5

Step 13: height[6]=1 == height[4]=1, no more pop, push index 6

Stack: [3,4,6]
Water trapped: 2

Why: Condition not met for popping index 4

Step 14: i=7 (height 3) > height[6]=1, pop index 6

Popped index 6, stack now [3,4]

Why: Current bar taller than top

Step 15: Calculate distance = 7 - 4 - 1 = 2, bounded height = min(3,1) - 1 = 0, water += 0

Water trapped: 2

Why: No water as bounded height is zero

Step 16: Still 3 > height[4]=1, pop index 4

Popped index 4, stack now [3]

Why: Continue popping smaller bars

Step 17: Calculate distance = 7 - 3 - 1 = 3, bounded height = min(3,2) - 1 = 1, water += 3

Water trapped: 5

Why: Water trapped between bars at indices 3 and 7 above indices 4 and 6

Step 18: Still 3 > height[3]=2, pop index 3

Popped index 3, stack now empty

Why: Continue popping

Step 19: Stack empty, no calculation, push index 7

Stack: [7]
Water trapped: 5

Why: Add current tall bar

Step 20: i=8 (height 2) < height[7]=3, push index 8

Stack: [7,8]
Water trapped: 5

Why: Shorter bar, push for potential trapping

Step 21: i=9 (height 1) < height[8]=2, push index 9

Stack: [7,8,9]
Water trapped: 5

Why: Shorter bar, push

Step 22: i=10 (height 2) > height[9]=1, pop index 9

Popped index 9, stack now [7,8]

Why: Taller than top

Step 23: Calculate distance = 10 - 8 - 1 = 1, bounded height = min(2,2) - 1 = 1, water += 1

Water trapped: 6

Why: Water trapped between 8 and 10 above 9

Step 24: height[10]=2 == height[8]=2, no pop, push index 10

Stack: [7,8,10]
Water trapped: 6

Why: Condition not met

Step 25: i=11 (height 1) < height[10]=2, push index 11

Stack: [7,8,10,11]
Water trapped: 6

Why: End of array, final state

Result:

Final trapped water = 6 units

Annotated Code

DSA C++

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

int trap(vector<int>& height) {
    int n = height.size();
    stack<int> st; // stores indices
    int water = 0;
    for (int i = 0; i < n; i++) {
        // While current bar is taller than top of stack bar
        while (!st.empty() && height[i] > height[st.top()]) {
            int top = st.top();
            st.pop(); // pop the smaller bar
            if (st.empty()) break; // no left boundary
            int distance = i - st.top() - 1; // width between left and right boundary
            int bounded_height = min(height[i], height[st.top()]) - height[top];
            water += distance * bounded_height; // add trapped water
        }
        st.push(i); // push current bar index
    }
    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;
}

while (!st.empty() && height[i] > height[st.top()]) {

Check if current bar is taller than top bar in stack to find trapped water

int top = st.top(); st.pop();

Pop the smaller bar to calculate trapped water over it

if (st.empty()) break;

Stop if no left boundary to trap water

int distance = i - st.top() - 1;

Calculate width between left and right boundaries

int bounded_height = min(height[i], height[st.top()]) - height[top];

Calculate height of trapped water bounded by left and right bars

water += distance * bounded_height;

Add trapped water volume for this segment

st.push(i);

Push current bar index for future trapping

Output

6

Complexity Analysis

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

Space: O(n) for the stack storing indices of bars

vs Alternative: Compared to the naive O(n^2) approach checking left and right max for each bar, this stack method is more efficient

Edge Cases

Empty height array

Returns 0 as no bars to trap water

DSA C++

for (int i = 0; i < n; i++) {

All bars of same height

Returns 0 as no space to trap water

DSA C++

while (!st.empty() && height[i] > height[st.top()]) {

Strictly increasing or decreasing bars

Returns 0 as no trapped water possible

DSA C++

while (!st.empty() && height[i] > height[st.top()]) {

When to Use This Pattern

When you need to find trapped water between bars or heights, and want an efficient O(n) solution, use the stack pattern to track boundaries and calculate trapped water.

Common Mistakes

Mistake: Not checking if stack is empty before accessing top after popping
Fix: Add a check to break the loop if stack becomes empty after popping

Mistake: Using height difference without bounding by min of left and right bars
Fix: Calculate bounded height as min of left and right bar heights minus the popped bar height

Summary

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

Use when you want an efficient O(n) solution to the trapping rain water problem.

The key insight is to use a stack to find left and right boundaries and calculate trapped water when a taller bar appears.

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