Trapping Rain Water Problem in DSA Go - Build from Scratch

Trapping Rain Water Problem

📖 Scenario: Imagine you have a row of walls of different heights. When it rains, water gets trapped between these walls. You want to find out how much water can be trapped after raining.

🎯 Goal: You will write a Go program to calculate the total amount of trapped rain water given the heights of the walls.

📋 What You'll Learn

Create a slice called heights with exact values representing wall heights

Create two slices leftMax and rightMax to store maximum heights from left and right

Use a loop to fill leftMax and rightMax based on heights

Calculate trapped water using the precomputed max arrays

Print the total trapped water as an integer

💡 Why This Matters

🌍 Real World

Calculating trapped rain water helps in designing drainage systems and understanding water flow in terrains.

💼 Career

This problem is a common interview question testing array manipulation, prefix/suffix computations, and problem-solving skills.

1

Create the wall heights slice

Create a slice called heights with these exact values: 0,1,0,2,1,0,1,3,2,1,2,1

DSA Go

# Create the slice heights with the given values
# Your code here

Hint

Use heights := []int{...} to create the slice with the exact values.

2

Create leftMax and rightMax slices

Create two slices called leftMax and rightMax with the same length as heights. Initialize them with zeros.

DSA Go

package main

func main() {
    heights := []int{0,1,0,2,1,0,1,3,2,1,2,1}
    // Create leftMax and rightMax slices with length equal to heights
    // Your code here
}

Hint

Use make([]int, len(heights)) to create slices of the same length as heights.

3

Fill leftMax and rightMax slices

Use a for loop with variable i from 0 to len(heights)-1 to fill leftMax so that each element is the maximum height from the left up to that index. Then use a for loop with variable i from len(heights)-1 down to 0 to fill rightMax so that each element is the maximum height from the right up to that index.

DSA Go

package main

func main() {
    heights := []int{0,1,0,2,1,0,1,3,2,1,2,1}
    leftMax := make([]int, len(heights))
    rightMax := make([]int, len(heights))
    // Fill leftMax from left to right
    // Your code here
    // Fill rightMax from right to left
    // Your code here
}

Hint

Use two loops: one from left to right to fill leftMax, and one from right to left to fill rightMax.

4

Calculate and print total trapped water

Create a variable totalWater set to 0. Use a for loop with variable i from 0 to len(heights)-1 to calculate trapped water at each index as the minimum of leftMax[i] and rightMax[i] minus heights[i]. Add this value to totalWater. Finally, print totalWater using fmt.Println(totalWater).

DSA Go

package main

import "fmt"

func main() {
    heights := []int{0,1,0,2,1,0,1,3,2,1,2,1}
    leftMax := make([]int, len(heights))
    rightMax := make([]int, len(heights))

    maxLeft := 0
    for i := 0; i  maxLeft {
            maxLeft = heights[i]
        }
        leftMax[i] = maxLeft
    }

    maxRight := 0
    for i := len(heights) - 1; i >= 0; i-- {
        if heights[i] > maxRight {
            maxRight = heights[i]
        }
        rightMax[i] = maxRight
    }

    // Calculate total trapped water and print it
    // Your code here
}

Hint

Calculate trapped water at each index as the smaller of leftMax and rightMax minus the height. Sum all positive trapped water values. Use fmt.Println to print the total.

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