Trapping Rain Water Problem in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the variable that stores the total trapped water.

DSA Go

totalWater := [1]

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

Anil

B1

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing totalWater to 1 or -1 instead of 0.

We start counting trapped water from zero, so initializing totalWater to 0 is correct.

2fill in blank

medium

Complete the code to update the left maximum height while iterating from the left.

DSA Go

if height[i] > [1] {
    leftMax = height[i]
}

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

ArightMax

BleftMax

CtotalWater

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with rightMax instead of leftMax.

We compare the current height with the left maximum height to update it.

3fill in blank

hard

Fix the error in the condition to decide which pointer to move.

DSA Go

if leftMax < [1] {
    left++
} else {
    right--
}

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

ArightMax

BleftMax

Cheight[left]

Dheight[right]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing leftMax with itself or with current heights.

The decision depends on comparing leftMax and rightMax to move pointers correctly.

4fill in blank

hard

Fill both blanks to calculate trapped water at the left pointer.

DSA Go

if height[left] < [1] {
    totalWater += [2] - height[left]
}

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

AleftMax

BrightMax

Cheight[right]

Dheight[left]

Attempts:

3 left

💡 Hint

Common Mistakes

Using rightMax or height[right] instead of leftMax.

Water trapped at left is difference between leftMax and current height[left].

5fill in blank

hard

Fill all three blanks to calculate trapped water at the right pointer.

DSA Go

if height[right] < [1] {
    totalWater += [2] - height[right]
}
right--

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

AleftMax

BrightMax

Cheight[right]

Dheight[left]

Attempts:

3 left

💡 Hint

Common Mistakes

Using leftMax or height[left] instead of rightMax.

Water trapped at right is difference between rightMax and current height[right].

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