Trapping Rain Water Using Stack in DSA C++ - Execution Trace

Concept Flow - Trapping Rain Water Using Stack

Start with empty stack

↓

Iterate over height array

↓

While stack not empty and current height > height at stack top

↓

Pop top from stack

↓

Calculate distance and bounded height

↓

Add trapped water

↓

Push current index to stack

↓

Move to next index

↓

End when all bars processed

↓

Return total trapped water

We scan bars left to right, using a stack to find boundaries that trap water. When current bar is taller than stack top, we pop and calculate trapped water between boundaries.

Execution Sample

DSA C++

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

Calculates trapped rain water by scanning bars and using a stack to find left and right boundaries.

Execution Table

Step	Operation	Current Index (i)	Stack Content (indices)	Popped Index	Distance	Bounded Height	Water Added	Total Water	Visual State
1	Push index 0	0	[0]	-	-	-	0	0	Height: [0,1,0,2,1,0,1,3,2,1,2,1]
2	Pop index 0	1	[]	0	-	-	0	0	Current height 1 > height[0]=0, pop and stack empty, break
3	Push index 1	1	[1]	-	-	-	0	0	Push index 1, height 1
4	Push index 2	2	[1,2]	-	-	-	0	0	Current height 0 <= stack top height 1, push
5	Pop index 2	3	[1]	2	3-1-1=1	min(2,1)-0=1	1	1	Current height 2 > height[2]=0, pop and calculate
6	Pop index 1	3	[]	1	-	-	-	1	Stack empty after pop, break
7	Push index 3	3	[3]	-	-	-	0	1	Push index 3, height 2
8	Push index 4	4	[3,4]	-	-	-	0	1	Push index 4, height 1
9	Push index 5	5	[3,4,5]	-	-	-	0	1	Push index 5, height 0
10	Pop index 5	6	[3,4]	5	6-4-1=1	min(1,1)-0=1	1	2	Water trapped between indices 4 and 6
11	Push index 6	6	[3,4,6]	-	-	-	0	2	Current height 1 == stack top height 1, push
12	Pop index 6	7	[3,4]	6	7-4-1=2	min(3,1)-1=0	0	2	Current height 3 > height[6]=1, pop and calculate
13	Pop index 4	7	[3]	4	7-3-1=3	min(3,2)-1=1	3	5	Water trapped between indices 3 and 7
14	Pop index 3	7	[]	3	-	-	-	5	Stack empty after pop, break
15	Push index 7	7	[7]	-	-	-	0	5	Push index 7, height 3
16	Push index 8	8	[7,8]	-	-	-	0	5	Push index 8, height 2
17	Push index 9	9	[7,8,9]	-	-	-	0	5	Push index 9, height 1
18	Pop index 9	10	[7,8]	9	10-8-1=1	min(2,2)-1=1	1	6	Water trapped between indices 8 and 10
19	Push index 10	10	[7,8,10]	-	-	-	0	6	Current height 2 == stack top height 2, push
20	Push index 11	11	[7,8,10,11]	-	-	-	0	6	Push index 11, height 1
21	Loop check	12	[7,8,10,11]	-	-	-	0	6	i >= height.size(), exit loop
22	End	12	[7,8,10,11]	-	-	-	0	6	All bars processed, total water trapped = 6

💡 All bars processed, stack traversal complete, total trapped water calculated

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 10	After Step 13	After Step 18	Final
i	0	1	3	6	7	10	12
stack	[]	[0]	[1]	[3,4]	[3]	[7,8]	[7,8,10,11]
water	0	0	1	2	5	6	6

Key Moments - 3 Insights

Why do we pop from the stack only when current height is greater than height at stack top?

Because popping happens only when we find a right boundary taller than the bar at stack top, allowing us to trap water between left and right boundaries (see execution_table steps 10 and 13).

Why do we break if the stack becomes empty after popping?

If the stack is empty, it means no left boundary exists to trap water with the current bar, so we stop calculating water for that popped bar (see execution_table steps 6 and 14).

How is the trapped water amount calculated after popping a bar?

We calculate distance between current index and new stack top minus one, then multiply by bounded height (minimum of current and stack top heights minus popped bar height), as shown in steps 10 and 13.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the water added and total water after this step?

A Water added = 1, Total water = 2

B Water added = 0, Total water = 0

C Water added = 3, Total water = 3

D Water added = 4, Total water = 4

💡 Hint

Check the 'Water Added' and 'Total Water' columns at step 10 in execution_table

At which step does the stack become empty after popping, causing a break in calculation?

A Step 6

B Step 11

C Step 14

D Step 18

💡 Hint

Look for 'Stack empty after pop, break' in the 'Visual State' column

If the height at index 5 was increased to 2, how would the trapped water change at step 10?

A Water added would increase

B Water added would decrease

C Water added would be zero

D Water added would remain the same

💡 Hint

Consider how bounded height is calculated using min of current and stack top heights minus popped bar height

Concept Snapshot

Trapping Rain Water Using Stack:
- Use a stack to store indices of bars.
- Iterate over bars, pop when current bar taller than stack top.
- Calculate trapped water using distance and bounded height.
- Add trapped water to total.
- Push current index to stack.
- Continue until all bars processed.

Full Transcript

This visualization shows how to calculate trapped rain water using a stack. We start with an empty stack and iterate over the height array. For each bar, if it is taller than the bar at the top of the stack, we pop from the stack and calculate trapped water between the current bar and the new top of the stack. We add this water to the total. If the stack becomes empty after popping, we stop calculating for that bar. We then push the current bar's index onto the stack and continue. The process repeats until all bars are processed. The total trapped water is returned at the end.

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