Trapping Rain Water Using Stack in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a stack to solve the Trapping Rain Water problem?

Use a stack to keep track of bars that are bounded by higher bars on both sides. When a higher bar is found, calculate trapped water with the bars in the stack.

beginner

In the stack approach, what does each element in the stack represent?

Each element represents the index of a bar in the height array, used to find boundaries for trapped water.

intermediate

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

Because we found a right boundary higher than the top bar, so we can calculate trapped water between the left boundary (new top) and current bar.

intermediate

What happens if the stack is empty after popping the top element during the water calculation?

No left boundary exists, so no water can be trapped for that popped bar.

advanced

How do you calculate the width and height of trapped water when a bounded region is found?

Width = distance between current index and new top of stack - 1; Height = min(height[current], height[new top]) - height[popped].

What data structure is used to solve the Trapping Rain Water problem in this approach?

A Array

B Queue

C Linked List

D Stack

The stack helps track bars and boundaries to calculate trapped water.

When do you calculate trapped water in the stack method?

A When current bar is taller than top of stack

B When current bar is shorter than top of stack

C At the end of the array only

D When stack is empty

Trapped water is calculated when a right boundary taller than the top bar is found.

What does the stack store in the Trapping Rain Water problem?

A Heights of bars

B Indices of bars

C Water volume

D Width of trapped water

Stack stores indices to access heights and calculate distances.

If the stack is empty after popping, what does it mean for trapped water calculation?

A Water can be trapped

B Water trapped equals height of popped bar

C No left boundary, so no water trapped

D Calculation continues with next bar

No left boundary means no trapped water for that segment.

How is the height of trapped water calculated?

A Min height of current and new top bar minus popped bar height

B Max height of current and popped bar

C Difference between current and popped bar heights

D Sum of heights of all bars in stack

Height is limited by the smaller boundary minus the bottom bar height.

Explain step-by-step how the stack helps calculate trapped rain water in the given height array.

Think about boundaries and how water is trapped between them.

Describe how to calculate the trapped water volume when a bounded region is found using the stack method.

Focus on how width and height define the trapped water area.

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