Trapping Rain Water Using Stack in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of trapping rain water calculation with given heights

What is the output of the following Go code that calculates trapped rain water using a stack?

DSA Go

package main

import "fmt"

func trap(height []int) int {
    stack := []int{}
    water := 0
    for i := 0; i < len(height); i++ {
        for len(stack) > 0 && height[i] > height[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(height[i], height[stack[len(stack)-1]]) - height[top]
            water += distance * boundedHeight
        }
        stack = append(stack, i)
    }
    return water
}

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

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

A 5

B 6

C 7

D 8

💡 Hint

Think about how the stack helps find boundaries to trap water between bars.

The code uses a stack to find the left and right boundaries for trapped water. It calculates trapped water by finding the distance between boundaries and the height difference. For the given heights, the total trapped water is 6 units.

❓ Predict Output

intermediate

Output of trapping rain water with uniform height bars

What is the output of this Go code that calculates trapped rain water using a stack for uniform height bars?

DSA Go

package main

import "fmt"

func trap(height []int) int {
    stack := []int{}
    water := 0
    for i := 0; i < len(height); i++ {
        for len(stack) > 0 && height[i] > height[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(height[i], height[stack[len(stack)-1]]) - height[top]
            water += distance * boundedHeight
        }
        stack = append(stack, i)
    }
    return water
}

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

func main() {
    heights := []int{3,3,3,3,3}
    fmt.Println(trap(heights))
}

A 0

B 3

C 5

D 15

💡 Hint

Uniform height bars cannot trap water between them.

Since all bars have the same height, no water can be trapped between them. The output is 0.

🔧 Debug

advanced

Identify the runtime error in trapping rain water code

What runtime error will this Go code produce when calculating trapped rain water using a stack?

DSA Go

package main

import "fmt"

func trap(height []int) int {
    stack := []int{}
    water := 0
    for i := 0; i <= len(height); i++ {
        for len(stack) > 0 && height[i] > height[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(height[i], height[stack[len(stack)-1]]) - height[top]
            water += distance * boundedHeight
        }
        stack = append(stack, i)
    }
    return water
}

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

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

A 6

B panic: invalid memory address or nil pointer dereference

C 0

D panic: runtime error: index out of range

💡 Hint

Check the loop condition and array indexing carefully.

The loop runs with i <= len(height), which causes an index out of range error when i equals len(height).

🧠 Conceptual

advanced

Why does the stack help in trapping rain water problem?

Which of the following best explains why a stack is used in the trapping rain water algorithm?

A It sorts the bars in ascending order to calculate trapped water.

B It stores the heights of water trapped at each position directly.

C It helps keep track of the indices of bars to find boundaries for trapped water efficiently.

D It reverses the array to calculate trapped water from right to left.

💡 Hint

Think about how boundaries are found between bars.

The stack stores indices of bars in a way that helps find left and right boundaries to calculate trapped water between them efficiently.

❓ Predict Output

expert

Output of trapping rain water with complex height pattern

What is the output of this Go code that calculates trapped rain water using a stack for a complex height pattern?

DSA Go

package main

import "fmt"

func trap(height []int) int {
    stack := []int{}
    water := 0
    for i := 0; i < len(height); i++ {
        for len(stack) > 0 && height[i] > height[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(height[i], height[stack[len(stack)-1]]) - height[top]
            water += distance * boundedHeight
        }
        stack = append(stack, i)
    }
    return water
}

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

func main() {
    heights := []int{4,2,0,3,2,5}
    fmt.Println(trap(heights))
}

A 9

B 7

C 10

D 8

💡 Hint

Visualize the bars and trapped water between them carefully.

The total trapped water for the given heights is 9 units, calculated by summing trapped water between boundaries found using the stack.

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