Trapping Rain Water Using Stack in DSA C++ - Deep Dive

Overview - Trapping Rain Water Using Stack

What is it?

Trapping Rain Water Using Stack is a method to find how much water can be trapped between bars of different heights after it rains. Imagine bars of varying heights placed side by side; water can collect in the dips between taller bars. This method uses a stack data structure to efficiently calculate the total trapped water by scanning the bars once.

Why it matters

Without this method, calculating trapped water would be slow and complicated, especially for large inputs. This algorithm solves the problem efficiently, saving time and computing resources. It helps in real-world scenarios like designing drainage systems or understanding how water accumulates in terrains.

Where it fits

Before learning this, you should understand arrays and basic stack operations. After mastering this, you can explore other water trapping methods like two-pointer techniques and dynamic programming approaches.

Mental Model

Core Idea

Use a stack to keep track of bars that can trap water when a taller bar appears, calculating trapped water by measuring the distance and height difference between bars.

Think of it like...

Imagine walking along a row of buildings with different heights holding buckets. When you find a taller building after shorter ones, you pour water into the buckets between them, measuring how much water each bucket can hold.

Index: 0   1   2   3   4   5   6
Height: 0 | 1 | 0 | 2 | 1 | 0 | 1
Stack: ┌─────┐
       │ 1   │  (height 1)
       │ 3   │  (height 2)
       └─────┘
Process: Push indices while heights rise or equal, pop when current height > top stack height to calculate trapped water between bars.

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

Concept: Introduce the problem of trapping rain water between bars of different heights.

Imagine a row of vertical bars with different heights. When it rains, water can collect in the spaces between taller bars if shorter bars are in between. The goal is to find the total amount of water trapped after raining.

Result

You understand the problem visually and conceptually: water is trapped where there are dips between taller bars.

Understanding the physical setup helps visualize why water accumulates and where to look for trapped water.

2

Foundation

Basics of Stack Data Structure

Concept: Learn what a stack is and how it works with push and pop operations.

A stack is like a pile of plates: you add (push) plates on top and remove (pop) from the top only. It follows Last-In-First-Out (LIFO) order. We use a stack to remember bars that might trap water later.

Result

You can use a stack to keep track of bars in order and retrieve the last added bar easily.

Knowing stack behavior is essential because the algorithm relies on pushing and popping bars to find trapped water.

3

Intermediate

Using Stack to Track Bars

🤔Before reading on: do you think the stack should store bar heights or their positions (indices)? Commit to your answer.

Concept: Store indices of bars in the stack to calculate distances and heights for trapped water.

We push indices of bars onto the stack. When we find a bar taller than the top of the stack, it means water can be trapped. We pop the top and calculate trapped water using the distance between current bar and new top of stack, and the height difference.

Result

The stack helps identify boundaries of trapped water and calculate volume efficiently.

Storing indices instead of heights allows calculation of width between bars, which is crucial for volume calculation.

4

Intermediate

Calculating Water Volume on Pop

🤔Before reading on: do you think trapped water depends on the height of the popped bar or the shorter of the two surrounding bars? Commit to your answer.

Concept: Water trapped depends on the shorter of the two bars surrounding the popped bar and the distance between them.

When popping a bar, calculate the distance between current bar and new top of stack minus one. The height of trapped water is the minimum height of current bar and new top minus the popped bar's height. Multiply distance by height to get trapped water volume.

Result

You can compute trapped water for each dip efficiently as you process bars.

Knowing that trapped water height depends on the shorter boundary prevents overestimating water volume.

5

Intermediate

Single Pass Algorithm Using Stack

Concept: Combine stack operations and water calculation in one pass through the array.

Initialize an empty stack and total water = 0. Iterate over bars: while current bar height > height at stack top, pop stack and calculate trapped water. Push current index onto stack. Continue until all bars processed.

Result

Total trapped water is calculated in one pass with O(n) time complexity.

A single pass with stack is efficient and avoids nested loops, making the algorithm scalable.

6

Advanced

Implementing the Algorithm in C++

🤔Before reading on: do you think the stack stores heights or indices in the code? Commit to your answer.

Concept: Write complete C++ code using stack to solve the trapping rain water problem.

#include #include #include #include int trap(const std::vector& height) { std::stack st; int water = 0; int n = height.size(); 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); } return water; } int main() { std::vector height = {0,1,0,2,1,0,1,3,2,1,2,1}; std::cout << "Trapped water: " << trap(height) << std::endl; return 0; }

Result

Trapped water: 6

Implementing the algorithm clarifies how stack operations and calculations work together to solve the problem efficiently.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think empty or uniform height arrays trap any water? Commit to your answer.

Concept: Understand how the algorithm behaves with edge cases and why it runs in linear time.

If the array is empty or all bars have the same height, no water is trapped. The stack-based algorithm processes each bar once, pushing and popping at most once, resulting in O(n) time. It uses O(n) space for the stack in worst case (strictly decreasing heights).

Result

Algorithm correctly returns zero for no-trap cases and runs efficiently for large inputs.

Knowing edge cases and performance guarantees helps in trusting and optimizing the algorithm in production.

Under the Hood

The stack stores indices of bars in non-increasing height order. When a taller bar appears, it signals a right boundary for trapping water. Popping the stack reveals the bottom of a container. The trapped water volume is calculated by the width between boundaries and the height difference. This process repeats until the current bar is no longer taller than the top of the stack.

Why designed this way?

This design avoids nested loops by using a stack to remember potential boundaries. Alternatives like brute force check all pairs, which is slow. The stack approach balances time and space complexity, making it practical for large datasets.

Input bars: 0 1 0 2 1 0 1 3 2 1 2 1
Stack process:
 ┌─────────────┐
 │ Push index 1│ height=1
 │ Push index 3│ height=2
 │ Current=3 > top=1, pop 1
 │ Calculate water trapped between 1 and 3
 │ Push current index
 └─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does the algorithm store bar heights in the stack? Commit yes or no.

Common Belief: The stack stores the heights of the bars directly.

Reality: The stack stores indices of bars, not their heights, to calculate distances between bars.

Why it matters: Storing heights would prevent calculating the width between bars, leading to incorrect water volume calculation.

Quick: Can trapped water height be more than the shorter boundary bar? Commit yes or no.

Common Belief: Water trapped can be as high as the tallest bar in the array.

Reality: Water height is limited by the shorter of the two boundary bars surrounding the trapped area.

Why it matters: Ignoring this leads to overestimating trapped water and incorrect results.

Quick: Does the algorithm require multiple passes over the array? Commit yes or no.

Common Belief: Calculating trapped water requires scanning the array multiple times.

Reality: The stack-based algorithm calculates trapped water in a single pass with O(n) time complexity.

Why it matters: Believing multiple passes are needed may cause inefficient implementations.

Quick: Is the stack size always small? Commit yes or no.

Common Belief: The stack will always hold only a few elements at a time.

Reality: In worst cases (strictly decreasing heights), the stack can grow to hold all indices, using O(n) space.

Why it matters: Underestimating space usage can cause memory issues in large inputs.

Expert Zone

1

The algorithm's efficiency depends on the monotonic nature of the stack, which ensures each bar is pushed and popped at most once.

2

Handling equal height bars carefully avoids counting trapped water incorrectly or missing trapped water between bars of the same height.

3

The stack approach can be adapted to solve similar problems like finding the largest rectangle in a histogram by modifying the calculation logic.

When NOT to use

Avoid using the stack method when memory is extremely limited or when input size is small enough that simpler brute force or two-pointer methods are faster and easier to implement.

Production Patterns

In production, this algorithm is used in terrain analysis, urban planning for drainage, and game development for simulating water flow. It is often combined with preprocessing steps or integrated into larger simulation pipelines.

Connections

Monotonic Stack

Builds-on

Understanding monotonic stacks helps grasp why the trapping rain water algorithm efficiently manages bar heights and boundaries.

Two-Pointer Technique

Alternative approach

Knowing the two-pointer method offers a space-optimized alternative and deepens understanding of how boundaries control trapped water.

Hydrology and Terrain Modeling

Real-world application

The algorithm models how water accumulates in valleys and depressions, linking computer science with earth sciences.

Common Pitfalls

#1 Pushing bar heights instead of indices onto the stack.

Wrong approach:

std::stack st;
for (int i = 0; i < height.size(); ++i) {
while (!st.empty() && height[i] > st.top()) {
int top = st.top();
st.pop();
// calculation using top as height
}
st.push(height[i]);
}

Correct approach:

std::stack st;
for (int i = 0; i < height.size(); ++i) {
while (!st.empty() && height[i] > height[st.top()]) {
int top = st.top();
st.pop();
// calculation using indices
}
st.push(i);
}

Root cause:

Confusing the need for position information (indices) with the actual bar heights.

#2 Calculating trapped water height using the taller boundary bar instead of the shorter one.

Wrong approach:

int bounded_height = std::max(height[i], height[st.top()]) - height[top];

Correct approach:

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

Root cause:

Misunderstanding that water level is limited by the shorter boundary.

#3 Not checking if the stack is empty before popping or calculating distance.

Wrong approach:

while (height[i] > height[st.top()]) {
int top = st.top();
st.pop();
int distance = i - st.top() - 1; // No check if stack empty
// calculation
}

Correct approach:

while (!st.empty() && height[i] > height[st.top()]) {
int top = st.top();
st.pop();
if (st.empty()) break;
int distance = i - st.top() - 1;
// calculation
}

Root cause:

Forgetting that popping can empty the stack, causing invalid access.

Key Takeaways

Trapping rain water using a stack efficiently calculates trapped water by tracking bars' indices and heights in a single pass.

The stack stores indices to measure distances between bars, which is essential for calculating trapped water volume.

Water trapped between bars is limited by the shorter of the two boundary bars, preventing overestimation.

The algorithm runs in linear time and uses stack space proportional to the input size in the worst case.

Understanding edge cases and stack behavior ensures correct and efficient implementation in real-world applications.

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