Trapping Rain Water Problem in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of trapping rain water calculation

What is the output of the following Go code that calculates trapped rain water for the given height array?

DSA Go

package main
import "fmt"
func trap(height []int) int {
    n := len(height)
    if n == 0 {
        return 0
    }
    leftMax := make([]int, n)
    rightMax := make([]int, n)
    leftMax[0] = height[0]
    for i := 1; i < n; i++ {
        if height[i] > leftMax[i-1] {
            leftMax[i] = height[i]
        } else {
            leftMax[i] = leftMax[i-1]
        }
    }
    rightMax[n-1] = height[n-1]
    for i := n - 2; i >= 0; i-- {
        if height[i] > rightMax[i+1] {
            rightMax[i] = height[i]
        } else {
            rightMax[i] = rightMax[i+1]
        }
    }
    water := 0
    for i := 0; i < n; i++ {
        minHeight := leftMax[i]
        if rightMax[i] < minHeight {
            minHeight = rightMax[i]
        }
        if minHeight > height[i] {
            water += minHeight - height[i]
        }
    }
    return water
}
func main() {
    height := []int{0,1,0,2,1,0,1,3,2,1,2,1}
    fmt.Println(trap(height))
}

A 7

B 5

C 6

D 8

💡 Hint

Think about the water trapped between the bars considering the highest bars on left and right.

The code calculates the trapped water by finding the maximum height to the left and right of each bar, then sums the water trapped at each position.

For the input array, the total trapped water is 6 units.

🧠 Conceptual

intermediate

Understanding the role of leftMax and rightMax arrays

In the Trapping Rain Water problem, what do the leftMax and rightMax arrays represent?

A leftMax[i] is the highest bar from the start to i; rightMax[i] is the highest bar from the end to i

B leftMax[i] is the height of the bar at i; rightMax[i] is the water trapped at i

C leftMax[i] and rightMax[i] store the total water trapped up to i

D leftMax[i] is the minimum height between bars; rightMax[i] is the maximum height between bars

💡 Hint

Think about how the algorithm finds boundaries to trap water.

leftMax[i] stores the tallest bar from the left up to index i.

rightMax[i] stores the tallest bar from the right up to index i.

These help determine the water level at each position.

🔧 Debug

advanced

Identify the error in this trapping rain water code snippet

What error will this Go code produce when run?

DSA Go

package main
import "fmt"
func trap(height []int) int {
    n := len(height)
    leftMax := make([]int, n)
    rightMax := make([]int, n)
    leftMax[0] = height[0]
    for i := 1; i <= n; i++ {
        if height[i] > leftMax[i-1] {
            leftMax[i] = height[i]
        } else {
            leftMax[i] = leftMax[i-1]
        }
    }
    return 0
}
func main() {
    fmt.Println(trap([]int{0,1,0,2}))
}

A outputs 0 without error

B runtime error: index out of range

C compilation error: undefined variable i

D compilation error: missing return statement

💡 Hint

Check the loop boundary conditions carefully.

The loop uses i <= n, but valid indices go from 0 to n-1.

Accessing height[i] when i == n causes an index out of range runtime error.

❓ Predict Output

advanced

Output of optimized two-pointer trapping rain water code

What is the output of this Go code using two pointers to calculate trapped rain water?

DSA Go

package main
import "fmt"
func trap(height []int) int {
    left, right := 0, len(height)-1
    leftMax, rightMax := 0, 0
    water := 0
    for left < right {
        if height[left] < height[right] {
            if height[left] >= leftMax {
                leftMax = height[left]
            } else {
                water += leftMax - height[left]
            }
            left++
        } else {
            if height[right] >= rightMax {
                rightMax = height[right]
            } else {
                water += rightMax - height[right]
            }
            right--
        }
    }
    return water
}
func main() {
    fmt.Println(trap([]int{4,2,0,3,2,5}))
}

A 7

B 8

C 10

D 9

💡 Hint

Visualize water trapped between bars from both ends moving inward.

The two-pointer approach calculates trapped water by moving pointers inward and updating max heights.

For the input, total trapped water is 9 units.

🧠 Conceptual

expert

Time complexity of trapping rain water algorithms

What is the time complexity of the two-pointer approach for the Trapping Rain Water problem and why?

A O(n) because each element is visited at most once by left and right pointers

B O(n^2) because nested loops check all pairs of bars

C O(log n) because the array is divided recursively

D O(n) because it uses sorting before calculation

💡 Hint

Consider how many times the pointers move across the array.

The two-pointer method moves left and right pointers inward, each visiting elements once.

Thus, the time complexity is linear, O(n).

Practice

1. What does the Trapping Rain Water problem ask you to find given an array of heights?

easy

A. The minimum height of the bars

B. The maximum height of the bars

C. The total amount of water that can be trapped between the bars after raining

D. The number of bars in the array

Solution

1. Step 1: Understand the problem context

   The problem gives an array representing heights of bars and asks how much water can be trapped between them after rain.

2. Step 2: Identify the goal

   The goal is to calculate the total volume of trapped water, not just heights or counts.

3. Final Answer:

   The total amount of water trapped between bars -> Option C

4. Quick Check:

   Trapping Rain Water = Total trapped water [OK]

Hint: Think of bars as walls holding water in gaps [OK]

Common Mistakes:

• Confusing trapped water with bar heights
• Counting bars instead of water volume
• Ignoring gaps between bars

2. Which of the following Go code snippets correctly initializes an integer slice to represent bar heights for the Trapping Rain Water problem?

easy

A. heights := new int[6]{4, 2, 0, 3, 2, 5}

B. heights := int[]{4, 2, 0, 3, 2, 5}

C. heights := [6]int{4, 2, 0, 3, 2, 5}

D. heights := []int{4, 2, 0, 3, 2, 5}

Solution

1. Step 1: Recall Go slice initialization syntax

   In Go, slices are initialized with []int{values}, arrays with [size]int{values}.

2. Step 2: Identify correct slice syntax

   heights := []int{4, 2, 0, 3, 2, 5} uses []int{...} which is correct for a slice. heights := [6]int{4, 2, 0, 3, 2, 5} is an array, also valid but less flexible.

3. Final Answer:

   heights := []int{4, 2, 0, 3, 2, 5} -> Option D

4. Quick Check:

   Slice syntax = []int{...} [OK]

Hint: Use []int{} for slices, [n]int{} for arrays [OK]

Common Mistakes:

• Using int[] like in other languages
• Trying to use new keyword for slices
• Confusing arrays and slices syntax

3. What is the output of the following Go code snippet that calculates trapped rain water?

package main
import "fmt"
func trap(height []int) int {
    left, right := 0, len(height)-1
    leftMax, rightMax := 0, 0
    water := 0
    for left < right {
        if height[left] < height[right] {
            if height[left] >= leftMax {
                leftMax = height[left]
            } else {
                water += leftMax - height[left]
            }
            left++
        } else {
            if height[right] >= rightMax {
                rightMax = height[right]
            } else {
                water += rightMax - height[right]
            }
            right--
        }
    }
    return water
}
func main() {
    fmt.Println(trap([]int{0,1,0,2,1,0,1,3,2,1,2,1}))
}

medium

A. 6

B. 5

C. 7

D. 8

Solution

1. Step 1: Understand two-pointer approach

   The code uses two pointers moving inward, tracking max heights on left and right to calculate trapped water.

2. Step 2: Trace the example input

   For input [0,1,0,2,1,0,1,3,2,1,2,1], the trapped water calculated by this method is 6 units.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Two-pointer trap water = 6 [OK]

Hint: Use two pointers and track max heights from both ends [OK]

Common Mistakes:

• Not updating max heights correctly
• Adding negative water amounts
• Confusing left and right pointer moves

4. Identify the bug in the following Go code for trapping rain water and select the correct fix:

func trap(height []int) int {
    left, right := 0, len(height)-1
    leftMax, rightMax := 0, 0
    water := 0
    for left <= right {
        if height[left] < height[right] {
            if height[left] > leftMax {
                leftMax = height[left]
            } else {
                water += leftMax - height[left]
            }
            left++
        } else {
            if height[right] > rightMax {
                rightMax = height[right]
            } else {
                water += rightMax - height[right]
            }
            right--
        }
    }
    return water
}

medium

A. Change '>' to '>=' in max height comparisons

B. Change loop condition to 'left < right' instead of 'left <= right'

C. Initialize water to 1 instead of 0

D. Swap left and right pointer initial values

Solution

1. Step 1: Analyze loop condition impact

   The loop uses 'left <= right', which causes double counting when left == right.

2. Step 2: Fix loop condition

   Changing to 'left < right' prevents overlap and corrects water calculation.

3. Final Answer:

   Change loop condition to 'left < right' instead of 'left <= right' -> Option B

4. Quick Check:

   Loop condition fix = 'left < right' [OK]

Hint: Use strict less than in two-pointer loops to avoid overlap [OK]

Common Mistakes:

• Using <= causes double counting
• Changing comparison operators incorrectly
• Incorrect pointer initialization

5. Given the heights array [5, 2, 1, 2, 1, 5], what is the total trapped rain water? Use the two-pointer approach to solve.

hard

A. 10

B. 12

C. 8

D. 14

Solution

1. Step 1: Initialize pointers and max heights

   left=0, right=5, leftMax=0, rightMax=0, water=0.

2. Step 2: Move pointers inward calculating trapped water

   - left=0 (height=5) >= leftMax(0), leftMax=5, left++ - left=1 (2) < right=5 (5), height[left]

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Two-pointer sum water = 10 [OK]

Hint: Sum min(leftMax, rightMax) - height at each step [OK]

Common Mistakes:

• Adding water twice for same positions
• Not updating max heights correctly
• Stopping loop too early