Trapping Rain Water Using Stack in DSA Go

Mental Model

We use a stack to keep track of bars that can trap water between taller bars on both sides.

Analogy: Imagine a row of walls of different heights. Water gets trapped in dips between taller walls. The stack helps us remember where these dips start and end.

height array: [0,1,0,2,1,0,1,3,2,1,2,1]
stack: empty
water trapped: 0

Dry Run Walkthrough

Input: height array: [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: push index 0 (height 0) onto stack

stack: [0]
water trapped: 0

Why: Start with first bar to compare with next bars

Step 2: push index 1 (height 1) onto stack since height[1] > height[0]

stack: [0,1]
water trapped: 0

Why: Current bar is taller, so push to stack to find potential right boundary

Step 3: push index 2 (height 0) because next bar height[2]=0 is less

stack: [0,1,2]
water trapped: 0

Why: Current bar is lower, so push to stack to find dips

Step 4: pop index 2 (height 0) because height[3]=2 > height[2], calculate trapped water

stack: [0,1]
water trapped: 1 (between index 1 and 3)

Why: Found right boundary taller than bottom, calculate water trapped in between

Step 5: pop index 1 (height 1) because height[3]=2 > height[1], calculate trapped water

stack: [0]
water trapped: 2 (additional water between index 0 and 3)

Why: Found right boundary taller than bottom, calculate trapped water

Step 6: push index 3 (height 2) onto stack

stack: [0,3]
water trapped: 2

Why: Push new taller bar as potential right boundary

Step 7: push index 4 (height 1) onto stack since height[4] < height[3]

stack: [0,3,4]
water trapped: 2

Why: Lower bar, push to stack to find dips

Step 8: push index 5 (height 0) because height[5]=0 is lower

stack: [0,3,4,5]
water trapped: 2

Why: Current bar lower, push to stack to track dips

Step 9: pop index 5 (height 0) because height[6]=1 > height[5], calculate trapped water

stack: [0,3,4]
water trapped: 3 (additional water between index 5 and 6)

Why: Found right boundary taller than bottom, calculate trapped water

Step 10: pop index 4 (height 1) because height[6]=1 >= height[4], calculate trapped water

stack: [0,3]
water trapped: 3

Why: Right boundary taller or equal, calculate trapped water (no additional water here)

Step 11: push index 6 (height 1) onto stack

stack: [0,3,6]
water trapped: 3

Why: Push new bar as potential boundary

Step 12: pop index 6 (height 1) because height[7]=3 > height[6], calculate trapped water

stack: [0,3]
water trapped: 6 (water trapped between index 6 and 7)

Why: Right boundary taller, calculate trapped water

Step 13: pop index 3 (height 2) because height[7]=3 > height[3], calculate trapped water

stack: [0]
water trapped: 8 (additional water between index 3 and 7)

Why: Right boundary taller, calculate trapped water

Step 14: push index 7 (height 3) onto stack

stack: [0,7]
water trapped: 8

Why: Push new tallest bar

Step 15: push index 8 (height 2) onto stack since height[8] < height[7]

stack: [0,7,8]
water trapped: 8

Why: Lower bar, push to stack

Step 16: push index 9 (height 1) onto stack since height[9] < height[8]

stack: [0,7,8,9]
water trapped: 8

Why: Lower bar, push to stack

Step 17: pop index 9 (height 1) because height[10]=2 > height[9], calculate trapped water

stack: [0,7,8]
water trapped: 9 (water trapped between index 9 and 10)

Why: Right boundary taller, calculate trapped water

Step 18: pop index 8 (height 2) because height[10]=2 >= height[8], calculate trapped water

stack: [0,7]
water trapped: 9

Why: Right boundary taller or equal, calculate trapped water (no additional water here)

Step 19: push index 10 (height 2) onto stack

stack: [0,7,10]
water trapped: 9

Why: Push new bar as potential boundary

Step 20: push index 11 (height 1) onto stack since height[11] < height[10]

stack: [0,7,10,11]
water trapped: 9

Why: Lower bar, push to stack

Result:

stack: [0,7,10,11]
water trapped: 9

Annotated Code

DSA Go

package main

import "fmt"

func trap(height []int) int {
    stack := []int{}
    water := 0
    for i := 0; i < len(height); i++ {
        // While current bar is taller than top of stack bar
        for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1] // pop top

            if len(stack) == 0 {
                break // no left boundary
            }

            distance := i - stack[len(stack)-1] - 1
            boundedHeight := min(height[i], height[stack[len(stack)-1]]) - height[top]
            water += distance * boundedHeight
        }
        stack = append(stack, i) // push current index
    }
    return water
}

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

func main() {
    height := []int{0,1,0,2,1,0,1,3,2,1,2,1}
    fmt.Println(trap(height))
}

for i := 0; i < len(height); i++ {

iterate over each bar to process trapping

for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {

while current bar taller than stack top, process trapped water

top := stack[len(stack)-1] stack = stack[:len(stack)-1]

pop the top bar as bottom of trapped water

if len(stack) == 0 { break }

no left boundary means no trapped water here

distance := i - stack[len(stack)-1] - 1

calculate width between current bar and new stack top

boundedHeight := min(height[i], height[stack[len(stack)-1]]) - height[top]

calculate height of trapped water bounded by left and right bars

water += distance * boundedHeight

add trapped water volume for this segment

stack = append(stack, i)

push current bar index as potential boundary

Output

9

Complexity Analysis

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

Space: O(n) for the stack in worst case when bars are in ascending order

vs Alternative: Compared to brute force O(n^2) checking left and right max for each bar, stack method is much faster

Edge Cases

empty height array

returns 0 as no bars to trap water

DSA Go

for i := 0; i < len(height); i++ {

all bars same height

returns 0 as no dips to trap water

DSA Go

for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {

strictly increasing bars

returns 0 as no trapped water

DSA Go

for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {

When to Use This Pattern

When you need to find trapped water between bars or heights, use the stack pattern to efficiently find boundaries and calculate trapped water in one pass.

Common Mistakes

Mistake: Not checking if stack is empty before calculating trapped water
Fix: Add a check to break if stack is empty after popping top

Mistake: Using height[top] instead of min of left and right boundaries for bounded height
Fix: Calculate bounded height as min of left and right bar heights minus bottom height

Summary

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

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

The stack helps track bars that form boundaries to trap water between them.

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