Trapping Rain Water Using Stack in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the stack for indices.

DSA Go

stack := make([]int, 0)
for i := 0; i < len(height); i++ {
    for len(stack) > 0 && height[i] > height[[1]] {
        top := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        // calculation here
    }
    stack = append(stack, i)
}

Drag options to blanks, or click blank then click option'

Astack[len(stack)-1]

Bi

C0

Dheight[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Using i instead of the top index of the stack.

Comparing with height[i] instead of height at stack top.

We compare the current height with the height at the top index of the stack, which is stack[len(stack)-1].

2fill in blank

medium

Complete the code to calculate the distance between current index and new stack top.

DSA Go

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

Drag options to blanks, or click blank then click option'

A1

B0

C2

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Not subtracting 1, causing off-by-one error.

Using 0 or negative numbers incorrectly.

Distance is the gap between current index and the new top of stack minus 1.

3fill in blank

hard

Fix the error in calculating bounded height for trapped water.

DSA Go

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

Drag options to blanks, or click blank then click option'

A0

Bi

Cstack[len(stack)-1]

Dtop

Attempts:

3 left

💡 Hint

Common Mistakes

Using i or stack top instead of the popped top index.

Subtracting wrong heights causing negative or wrong values.

The bounded height is the difference between the smaller boundary height and the height at the popped top index.

4fill in blank

hard

Fill both blanks to correctly update the total trapped water.

DSA Go

water += [1] * [2]

Drag options to blanks, or click blank then click option'

Adistance

BboundedHeight

Cheight[i]

Dtop

Attempts:

3 left

💡 Hint

Common Mistakes

Multiplying wrong variables like height[i] or top.

Adding instead of multiplying.

Total trapped water is the area: width (distance) times height (boundedHeight).

5fill in blank

hard

Fill all three blanks to complete the min function and the loop condition.

DSA Go

func min(a, b int) int {
    if a [1] b {
        return a
    }
    return b
}

for i := 0; i < len(height) && height[i] [2] height[stack[len(stack)-1]]; i++ {
    top := stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    boundedHeight := min(height[i], height[stack[len(stack)-1]]) - height[top]
    distance := i - stack[len(stack)-1] - 1
    water += distance * boundedHeight
}

Drag options to blanks, or click blank then click option'

A<

B>

C>=

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operators causing logic errors.

Confusing '<' and '>' in min function and loop condition.

The min function returns the smaller value using '<'. The loop continues while current height is greater than the height at stack top using '>'.

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