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

↓

Calculate trapped water

↓

Add water to total

↓

Push current index to stack

↓

Move to next index

↓

End when all bars processed

↓

Return total trapped water

We use a stack to keep indexes of bars. When current bar is higher than stack top, we pop and calculate trapped water between bars.

Execution Sample

DSA C

int trap(int* height, int heightSize) {
    int stack[heightSize];
    int top = -1, water = 0, i = 0;
    while (i < heightSize) {
        while (top != -1 && height[i] > height[stack[top]]) {
            int topIndex = stack[top--];
            if (top == -1) break;
            int distance = i - stack[top] - 1;
            int bounded_height = (height[i] < height[stack[top]] ? height[i] : height[stack[top]]) - height[topIndex];
            water += distance * (bounded_height > 0 ? bounded_height : 0);
        }
        stack[++top] = i++;
    }
    return water;
}

This code calculates trapped rain water using a stack to track bars and compute trapped water when a higher bar is found.

Execution Table

Step	Operation	Current Index (i)	Stack Content (indexes)	Popped Index	Distance	Bounded Height	Water Added	Total Water	Visual State
1	Push index 0	0	[0]	-	-	-	0	0	Height: [0:0] Stack: [0] Water: 0
2	Pop index 0 (height 0 < current height 1? Yes)	1	[]	0	-	-	0	0	Height: [0:0,1:1] Stack: [] Water: 0
3	Push index 1	1	[1]	-	-	-	0	0	Height: [0:0,1:1] Stack: [1] Water: 0
4	Push index 2	2	[1,2]	-	-	-	0	0	Height: [0:0,1:1,2:0] Stack: [1,2] Water: 0
5	Pop index 2 (height 0 < current height 3? Yes)	3	[1]	2	3 - 1 - 1 = 1	min(3,1) - 0 = 1	1*1=1	1	Height: [0:0,1:1,2:0,3:3] Stack: [1] Water: 1
6	Pop index 1 (height 1 < current height 3? Yes)	3	[]	1	-	-	0	1	Height: [0:0,1:1,2:0,3:3] Stack: [] Water: 1
7	Push index 3	3	[3]	-	-	-	0	1	Height: [0:0,1:1,2:0,3:3] Stack: [3] Water: 1
8	Push index 4	4	[3,4]	-	-	-	0	1	Height: [0:0,1:1,2:0,3:3,4:0] Stack: [3,4] Water: 1
9	Pop index 4 (height 0 < current height 2? Yes)	5	[3]	4	5 - 3 - 1 = 1	min(2,3) - 0 = 2	1*2=2	3	Height: [0:0,1:1,2:0,3:3,4:0,5:2] Stack: [3] Water: 3
10	Push index 5	5	[3,5]	-	-	-	0	3	Height: [0:0,1:1,2:0,3:3,4:0,5:2] Stack: [3,5] Water: 3
11	Push index 6	6	[3,5,6]	-	-	-	0	3	Height: [0:0,1:1,2:0,3:3,4:0,5:2,6:1] Stack: [3,5,6] Water: 3
12	Pop index 6 (height 1 < current height 4? Yes)	7	[3,5]	6	7 - 5 - 1 = 1	min(4,2) - 1 = 1	1*1=1	4	Height: [0:0,1:1,2:0,3:3,4:0,5:2,6:1,7:4] Stack: [3,5] Water: 4
13	Pop index 5 (height 2 < current height 4? Yes)	7	[3]	5	7 - 3 - 1 = 3	min(4,3) - 2 = 1	3*1=3	7	Height: [0:0,1:1,2:0,3:3,4:0,5:2,6:1,7:4] Stack: [3] Water: 7
14	Pop index 3 (height 3 < current height 4? Yes)	7	[]	3	-	-	0	7	Height: [0:0,1:1,2:0,3:3,4:0,5:2,6:1,7:4] Stack: [] Water: 7
15	Push index 7	7	[7]	-	-	-	0	7	Height: [0:0,1:1,2:0,3:3,4:0,5:2,6:1,7:4] Stack: [7] Water: 7
16	Push index 8	8	[7,8]	-	-	-	0	7	Height: [0:0,1:1,2:0,3:3,4:0,5:2,6:1,7:4,8:0] Stack: [7,8] Water: 7
17	Pop index 8 (height 0 < current height 2? Yes)	9	[7]	8	9 - 7 - 1 = 1	min(2,4) - 0 = 2	1*2=2	9	Height: [0:0,1:1,2:0,3:3,4:0,5:2,6:1,7:4,8:0,9:2] Stack: [7] Water: 9
18	Push index 9	9	[7,9]	-	-	-	0	9	Height: [0:0,1:1,2:0,3:3,4:0,5:2,6:1,7:4,8:0,9:2] Stack: [7,9] Water: 9
19	Pop index 9 (height 2 < current height 3? Yes)	10	[7]	9	10 - 7 - 1 = 2	min(3,4) - 2 = 1	2*1=2	11	Height: [0:0,1:1,2:0,3:3,4:0,5:2,6:1,7:4,8:0,9:2,10:3] Stack: [7] Water: 11
20	Push index 10	10	[7,10]	-	-	-	0	11	Height: [0:0,1:1,2:0,3:3,4:0,5:2,6:1,7:4,8:0,9:2,10:3] Stack: [7,10] Water: 11

💡 All bars processed, total trapped water calculated

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 9	After Step 13	After Step 18	Final
i	0	1	3	5	7	10	11
stack (indexes)	[]	[0]	[1]	[3]	[3]	[7,9]	[7,10]
water	0	0	1	3	7	9	11

Key Moments - 3 Insights

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

Because trapped water can only be formed when we find a right boundary higher than the previous bars. This is shown in execution_table rows 5 and 9 where popping happens only when current height is greater.

Why do we calculate distance as i - stack[top] - 1?

Distance is the width between the current bar and the new top of stack after popping. The '-1' excludes the popped bar itself. See execution_table rows 5 and 9 for distance calculation.

Why do we break if stack becomes empty after popping?

If stack is empty, there is no left boundary to trap water. So we stop calculating water for that popped bar. This is shown in execution_table row 6 where break happens after popping.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the amount of water added?

A 1

B 0

C 2

D 3

💡 Hint

Check the 'Water Added' column at step 5 in execution_table.

At which step does the total trapped water first become greater than zero?

A Step 1

B Step 5

C Step 9

D Step 13

💡 Hint

Look at the 'Total Water' column in execution_table to find when it changes from 0.

If the height at index 3 was lower, how would that affect the water trapped at step 13?

A Water trapped would increase

B Water trapped would stay the same

C Water trapped would decrease

D No water would be trapped at all

💡 Hint

Step 13 depends on height at index 3 as left boundary; lower height reduces bounded height.

Concept Snapshot

Trapping Rain Water Using Stack:
- Use a stack to store indexes of bars.
- Iterate bars, pop when current bar is higher than stack top.
- Calculate trapped water using distance and bounded height.
- Add trapped water to total.
- Push current index to stack.
- Return total water after processing all bars.

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. When the current bar is higher than the bar at the top of the stack, we pop the stack to find trapped water between bars. We calculate the distance between the current bar and the new top of the stack and find the bounded height to compute trapped water. We add this water to the total. We continue pushing indexes to the stack and repeat 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 reverse the order of the bars

B. To store the total amount of trapped water directly

C. To sort the heights of bars in ascending order

D. To keep track of bars that are not yet processed for water trapping

Solution

1. Step 1: Understand stack role in the algorithm

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

2. Step 2: Clarify what the stack does not do

   The stack does not store water amounts or sort bars; it helps find boundaries for trapped water.

3. Final Answer:

   To keep track of bars that are not yet processed for water trapping -> Option D

4. Quick Check:

   Stack tracks bars for trapping water [OK]

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

Common Mistakes:

• Thinking stack stores water volume directly
• Assuming stack sorts the bars
• Believing stack reverses bar order

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

easy

A. int stack[100]; int top = -1;

B. int stack; int top = 0;

C. int *stack = NULL; int top = 1;

D. int stack[] = {}; int top = -1;

Solution

1. Step 1: Check stack declaration syntax

   int stack[100]; int top = -1; declares an integer array with fixed size and initializes top to -1, which is correct for stack implementation.

2. Step 2: Identify incorrect declarations

   Options B, C, and D have wrong types or invalid initializations for stack and top pointer.

3. Final Answer:

   int stack[100]; int top = -1; -> Option A

4. Quick Check:

   Array + top = -1 is correct stack setup [OK]

Hint: Use array and top = -1 for empty stack [OK]

Common Mistakes:

• Using uninitialized or wrong top value
• Declaring stack as single int instead of array
• Using empty array syntax invalid in C

3. What is the output of the following code snippet that calculates trapped rain water using stack?

int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
int n = 12;
// Assume correct trapping rain water stack code runs here
int trapped = trappingRainWater(height, n);
printf("%d\n", trapped);

medium

A. 5

B. 6

C. 4

D. 7

Solution

1. Step 1: Understand the input heights

   The array represents bar heights where water can be trapped between taller bars.

2. Step 2: Calculate trapped water manually or recall known result

   The known trapped water for this input is 6 units.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Standard example trapped water = 6 [OK]

Hint: Remember classic example traps 6 units water [OK]

Common Mistakes:

• Miscounting trapped water units
• Confusing indexes or heights
• Assuming output is sum of heights

4. Identify the bug in this snippet of the trapping rain water stack algorithm:

while (top != -1 && height[i] > height[stack[top]]) {
  int topIndex = stack[top--];
  int distance = i - stack[top] - 1;
  int bounded_height = min(height[i], height[stack[top]]) - height[topIndex];
  water += distance * bounded_height;
}

medium

A. Using 'min' function without including its definition or header

B. Incorrect calculation of 'distance' by missing parentheses

C. Wrong decrement of 'top' causing stack underflow

D. Using 'water' variable without initialization

Solution

1. Step 1: Check function usage

   The code uses 'min' function but C standard library does not have 'min' by default; it needs a macro or function definition.

2. Step 2: Verify other parts

   Distance calculation and top decrement are correct; water variable usage depends on context but usually initialized.

3. Final Answer:

   Using 'min' function without including its definition or header -> Option A

4. Quick Check:

   min() undefined in C without custom code [OK]

Hint: Remember C needs custom min function or macro [OK]

Common Mistakes:

• Assuming min() is built-in in C
• Miscalculating distance with wrong parentheses
• Forgetting to initialize water variable

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

hard

A. 8

B. 7

C. 9

D. 6

Solution

1. Step 1: Analyze the heights for trapped water

   Water trapped at each position i is max(0, min(left_max[i], right_max[i]) - height[i]), where left_max is tallest bar strictly to the left, right_max strictly to the right. Stack method yields same result.

2. Step 2: Calculate trapped water step-by-step

   - i=1: min(4,5)-2 = 2
   - i=2: min(4,5)-0 = 4
   - i=3: min(4,5)-3 = 1
   - i=4: min(4,5)-2 = 2
   Total: 2+4+1+2 = 9 units.

3. Final Answer:

   9 -> Option C

4. Quick Check:

   Total trapped water = 9 [OK]

Hint: Sum water trapped between boundaries carefully [OK]

Common Mistakes:

• Double counting trapped water
• Ignoring zero height bars
• Misidentifying boundaries