Trapping Rain Water Using Stack in DSA Go - 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 trapped water

↓

Add trapped water to total

↓

Push current index to stack

↓

Repeat until end of array

↓

Return total trapped water

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

Execution Sample

DSA Go

heights := []int{0,1,0,2,1,0,1,3,2,1,2,1}
stack := []int{}
totalWater := 0
for i, h := range heights {
  // process stack and calculate water
}

This code calculates trapped rain water by iterating heights and using a stack to find boundaries.

Execution Table

Step	Operation	Stack (indexes)	Current Index	Current Height	Popped Index	Water Trapped	Visual State
1	Start	[]	-	-	-	0	[]
2	Push index 0	[0]	0	0	-	0	[0] height=0
3	Push index 1	[0,1]	1	1	-	0	[0,1] heights=0,1
4	Pop index 1	[0]	2	0	1	0	[0] height=0
5	Push index 2	[0,2]	2	0	-	0	[0,2] heights=0,0
6	Pop index 2	[0]	3	2	2	2	[0] height=0; trapped 2 units between 0 and 3
7	Pop index 0	[]	3	2	0	2	[]; trapped 2 units
8	Push index 3	[3]	3	2	-	2	[3] height=2
9	Push index 4	[3,4]	4	1	-	2	[3,4] heights=2,1
10	Push index 5	[3,4,5]	5	0	-	2	[3,4,5] heights=2,1,0
11	Pop index 5	[3,4]	6	1	5	2	[3,4] heights=2,1; trapped 0 units
12	Pop index 4	[3]	6	1	4	3	[3] height=2; trapped 1 unit between 4 and 6
13	Push index 6	[3,6]	6	1	-	3	[3,6] heights=2,1
14	Pop index 6	[3]	7	3	6	3	[3] height=2; trapped 0 units
15	Pop index 3	[]	7	3	3	5	[]; trapped 2 units between 3 and 7
16	Push index 7	[7]	7	3	-	5	[7] height=3
17	Push index 8	[7,8]	8	2	-	5	[7,8] heights=3,2
18	Push index 9	[7,8,9]	9	1	-	5	[7,8,9] heights=3,2,1
19	Pop index 9	[7,8]	10	2	9	5	[7,8] heights=3,2; trapped 0 units
20	Pop index 8	[7]	10	2	8	6	[7] height=3; trapped 1 unit between 8 and 10
21	Push index 10	[7,10]	10	2	-	6	[7,10] heights=3,2
22	Pop index 10	[7]	11	1	10	6	[7] height=3; trapped 0 units
23	Push index 11	[7,11]	11	1	-	6	[7,11] heights=3,1
24	End	[7,11]	-	-	-	6	Total trapped water = 6 units

💡 Reached end of array; total trapped water calculated

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 13	After Step 16	After Step 21	Final
stack	[]	[0]	[0,2]	[3]	[3,6]	[7]	[7,10]	[7,11]
totalWater	0	0	0	2	3	5	6	6
currentIndex	-	0	2	3	6	7	10	11
currentHeight	-	0	0	2	1	3	2	1

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 them (see steps 6, 12, 15).

What does the popped index represent in the calculation?

The popped index is the bottom of the valley where water can be trapped. We calculate trapped water between the left boundary (new stack top) and current index (see steps 6, 12, 15).

Why do we push the current index after popping?

We push current index to mark a new boundary or potential valley bottom for future trapping (see steps 8, 13, 16).

Visual Quiz - 3 Questions

Look at the execution table at step 6. What is the water trapped at this step?

A 2 units

B 0 units

C 1 unit

D 3 units

💡 Hint

Check the 'Water Trapped' column at step 6 in the execution_table.

At which step does the total trapped water first increase to 4 units?

A Step 12

B Step 20

C Step 15

D Step 24

💡 Hint

Look at the 'totalWater' variable in variable_tracker and the 'Water Trapped' column in execution_table.

If the height at index 7 was lower, how would the stack state change after step 16?

A Stack would be empty

B Stack would have more elements

C Stack would have fewer elements

D Stack would remain the same

💡 Hint

Consider how pushing and popping depend on current height compared to stack top height.

Concept Snapshot

Trapping Rain Water Using Stack:
- Use a stack to store indexes of bars
- Iterate heights, pop when current height > stack top height
- Calculate trapped water using popped index and boundaries
- Push current index after processing
- Sum trapped water for total
- Efficient O(n) solution using stack

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 height is greater than the height 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 trapped water to the total. Then we push the current index onto the stack. This process continues until we reach the end of the array. The stack helps us find boundaries for trapping water efficiently. The total trapped water is the sum of all trapped units calculated during popping. Key moments include understanding why popping happens only when current height is greater, what the popped index represents, and why we push the current index after popping. The final total trapped water for the sample input is 6 units.

Practice

1. What is the main purpose of using a stack in the Trapping Rain Water Using Stack algorithm?

easy

A. To keep track of the indices of bars to calculate trapped water

B. To store the heights of the bars directly

C. To sort the bars in ascending order

D. To reverse the array of bar heights

Solution

1. Step 1: Understand the role of stack

   The stack stores indices of bars, not heights, to help find boundaries for trapped water.

2. Step 2: Use indices to calculate trapped water

   By using indices, we can calculate width and height of trapped water between bars.

3. Final Answer:

   To keep track of the indices of bars to calculate trapped water -> Option A

4. Quick Check:

   Stack stores indices, not heights [OK]

Hint: Stack stores indices to find water boundaries quickly [OK]

Common Mistakes:

• Thinking stack stores heights instead of indices
• Assuming stack sorts bars
• Using stack to reverse array

2. Which of the following Go code snippets correctly declares an empty stack to be used for trapping rain water calculation?

easy

A. stack := []string{}

B. stack := make(map[int]int)

C. var stack []int

D. var stack int

Solution

1. Step 1: Identify correct stack type

   Stack should be a slice of integers to store indices, so var stack []int is correct.

2. Step 2: Check other options

   stack := make(map[int]int) uses a map, not a stack. stack := []string{} uses string slice, wrong type. var stack int is a single int, not a stack.

3. Final Answer:

   var stack []int -> Option C

4. Quick Check:

   Stack as int slice = var stack []int [OK]

Hint: Use slice of int for stack of indices in Go [OK]

Common Mistakes:

• Using map instead of slice for stack
• Using wrong data type like string
• Declaring stack as single int variable

3. What is the output of the following Go code snippet that uses stack to calculate trapped rain water?

heights := []int{0,1,0,2,1,0,1,3,2,1,2,1}
stack := []int{}
water := 0
for i := 0; i < len(heights); i++ {
    for len(stack) > 0 && heights[i] >= heights[stack[len(stack)-1]] {
        top := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if len(stack) == 0 {
            break
        }
        distance := i - stack[len(stack)-1] - 1
        boundedHeight := min(heights[i], heights[stack[len(stack)-1]]) - heights[top]
        water += distance * boundedHeight
    }
    stack = append(stack, i)
}
fmt.Println(water)

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

medium

A. 8

B. 5

C. 7

D. 6

Solution

1. Step 1: Trace the stack and water calculation

   The code implements the standard stack-based trapping rain water algorithm on the given heights array.

2. Step 2: Calculate trapped water for given input

   For input {0,1,0,2,1,0,1,3,2,1,2,1}, trapped water is 6 units.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Standard example input yields 6 units trapped water [OK]

Hint: Use known example array for quick trapped water = 6 [OK]

Common Mistakes:

• Miscounting trapped water units
• Ignoring stack empty check
• Wrong min height calculation

4. Identify the bug in the following Go code snippet for trapping rain water using stack:

heights := []int{4,2,0,3,2,5}
stack := []int{}
water := 0
for i := 0; i < len(heights); i++ {
    for len(stack) > 0 && heights[i] > heights[stack[len(stack)-1]] {
        top := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if len(stack) == 0 {
            break
        }
        distance := i - stack[len(stack)-1] - 1
        boundedHeight := min(heights[i], heights[stack[len(stack)-1]]) - heights[top]
        water += distance * boundedHeight
    }
    stack = append(stack, i)
}
fmt.Println(water)

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

What is the bug?

medium

A. Using '>' instead of '>=' in the inner loop condition

B. Not checking if stack is empty before popping

C. Incorrect calculation of distance between bars

D. Using min function incorrectly

Solution

1. Step 1: Analyze inner loop condition

   The condition uses '>' but it should be '>=' to correctly handle equal height bars.

2. Step 2: Effect of wrong condition

   Using '>' skips popping when heights are equal, causing incorrect trapped water calculation.

3. Final Answer:

   Using '>' instead of '>=' in the inner loop condition -> Option A

4. Quick Check:

   Use '>=' to handle equal heights correctly [OK]

Hint: Use '>=' in condition to pop equal or smaller bars [OK]

Common Mistakes:

• Using '>' instead of '>=' causing missed pops
• Not checking stack empty before pop (though code does)
• Miscomputing distance or bounded height

5. Given the heights array []int{3, 0, 2, 0, 4}, how much water will be trapped using the stack-based algorithm? Also, explain why the stack helps in this case.

hard

A. 6 units

B. 7 units

C. 5 units

D. 4 units

Solution

1. Step 1: Calculate trapped water manually

   Water at pos1: 3 units, pos2: 1 unit, pos3: 3 units. Total trapped water = 7 units.

2. Step 2: Explain stack role

   The stack stores indices of bars to find left and right boundaries for water trapping, allowing calculation of width and height of trapped water efficiently.

3. Final Answer:

   7 units -> Option B

4. Quick Check:

   Stack trace or min(leftmax,rightmax)-h sum = 7 units [OK]

Hint: Sum trapped water between boundaries using stack indices [OK]

Common Mistakes:

• Miscounting trapped water between bars
• Not understanding stack helps find boundaries
• Ignoring zero height bars in calculation