Trapping Rain Water Using Stack in DSA Go - Build from Scratch

Trapping Rain Water Using Stack

📖 Scenario: Imagine you have a row of buildings with different heights. When it rains, water gets trapped between these buildings. You want to find out how much water is trapped after the rain stops.

🎯 Goal: Build a Go program that uses a stack to calculate the total amount of trapped rainwater between buildings of different heights.

📋 What You'll Learn

Create a slice called heights with exact building heights

Create a stack using a slice of integers called stack

Use a loop to process each building height and calculate trapped water

Print the total trapped water as an integer

💡 Why This Matters

🌍 Real World

Calculating trapped rainwater helps in urban planning and drainage system design to prevent flooding.

💼 Career

Understanding stack-based algorithms and problem solving is useful for software engineering roles involving data structures and algorithm optimization.

1

Create the building heights slice

Create a slice of integers called heights with these exact values: 0,1,0,2,1,0,1,3,2,1,2,1

DSA Go

# Create the heights slice with given values
# Your code here

Hint

Use heights := []int{...} to create the slice with the exact numbers.

2

Create the stack slice and total water variable

Create an empty slice of integers called stack and an integer variable called totalWater set to 0

DSA Go

package main

func main() {
    heights := []int{0,1,0,2,1,0,1,3,2,1,2,1}
    // Create stack slice and totalWater variable
    // Your code here
}

Hint

Use stack := []int{} to create an empty stack and totalWater := 0 to start counting water.

3

Calculate trapped water using stack

Use a for loop with variable i from 0 to len(heights). Inside the loop, use a for loop to check if stack is not empty and heights[i] is greater than heights[stack[len(stack)-1]]. Pop the top of the stack into top. If the stack becomes empty, break. Calculate the distance as i - stack[len(stack)-1] - 1 and bounded height as the minimum of heights[i] and heights[stack[len(stack)-1]] minus heights[top]. Add distance * boundedHeight to totalWater. After the inner loop, append i to stack.

DSA Go

package main

func main() {
    heights := []int{0,1,0,2,1,0,1,3,2,1,2,1}
    stack := []int{}
    totalWater := 0

    // Calculate trapped water using stack
    // Your code here
}

Hint

Use two nested loops: the outer loop goes through each building, the inner loop pops from stack while current height is greater. Calculate trapped water by distance and bounded height.

4

Print the total trapped water

Use fmt.Println(totalWater) to print the total trapped water. Remember to import fmt at the top.

DSA Go

package main

import "fmt"

func main() {
    heights := []int{0,1,0,2,1,0,1,3,2,1,2,1}
    stack := []int{}
    totalWater := 0

    for i := 0; i  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]
            totalWater += distance * boundedHeight
        }
        stack = append(stack, i)
    }

    // Print the total trapped water
    // Your code here
}

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

Hint

Use fmt.Println(totalWater) to show the result. Don't forget to import fmt.

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