Trapping Rain Water Problem in DSA Go

Mental Model

Imagine bars of different heights and water trapped between them after rain. We want to find how much water stays trapped between these bars.

Analogy: Think of a row of buildings with different heights after rain. Water collects in the dips between taller buildings, like puddles trapped between walls.

Height bars: 3 0 2 0 4
Visual:
3 ↑       
2     ↑   
1   ↑   ↑ 
0 ↑   ↑   ↑
  0 1 2 3 4  (index)

Dry Run Walkthrough

Input: heights: [3, 0, 2, 0, 4]

Goal: Calculate total trapped water between bars

Step 1: Calculate max height to the left of each bar

leftMax = [3, 3, 3, 3, 4]

Why: We need to know the tallest bar on the left to know how much water can be trapped

Step 2: Calculate max height to the right of each bar

rightMax = [4, 4, 4, 4, 4]

Why: We need to know the tallest bar on the right to know how much water can be trapped

Step 3: Calculate trapped water at each bar by min(leftMax, rightMax) - height

water trapped per bar = [min(3,4)-3=0, min(3,4)-0=3, min(3,4)-2=1, min(3,4)-0=3, min(4,4)-4=0]

Why: Water trapped depends on the shorter side minus the bar height

Step 4: Sum trapped water values

total water = 0 + 3 + 1 + 3 + 0 = 7

Why: Total trapped water is sum of water trapped at each bar

Result:

Total trapped water = 7 units

Annotated Code

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++ {
        leftMax[i] = max(leftMax[i-1], height[i])
    }

    rightMax[n-1] = height[n-1]
    for i := n - 2; i >= 0; i-- {
        rightMax[i] = max(rightMax[i+1], height[i])
    }

    water := 0
    for i := 0; i < n; i++ {
        trapped := min(leftMax[i], rightMax[i]) - height[i]
        if trapped > 0 {
            water += trapped
        }
    }

    return water
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    heights := []int{3, 0, 2, 0, 4}
    result := trap(heights)
    fmt.Printf("Total trapped water = %d units\n", result)
}

leftMax[0] = height[0] for i := 1; i < n; i++ { leftMax[i] = max(leftMax[i-1], height[i]) }

Build left max array to know tallest bar on left for each position

rightMax[n-1] = height[n-1] for i := n - 2; i >= 0; i-- { rightMax[i] = max(rightMax[i+1], height[i]) }

Build right max array to know tallest bar on right for each position

for i := 0; i < n; i++ { trapped := min(leftMax[i], rightMax[i]) - height[i] if trapped > 0 { water += trapped } }

Calculate trapped water at each bar and sum it

Output

Total trapped water = 7 units

Complexity Analysis

Time: O(n) because we traverse the height array a few times but only linearly

Space: O(n) because we use two extra arrays leftMax and rightMax of size n

vs Alternative: Compared to a naive approach checking left and right max for each bar separately (O(n^2)), this is much faster using precomputed arrays

Edge Cases

empty height array

returns 0 as no bars means no trapped water

DSA Go

if n == 0 {
    return 0
}

all bars same height

returns 0 as no dips to trap water

DSA Go

trapped := min(leftMax[i], rightMax[i]) - height[i]
if trapped > 0 {
    water += trapped
}

strictly increasing or decreasing bars

returns 0 as water cannot be trapped on edges

DSA Go

trapped := min(leftMax[i], rightMax[i]) - height[i]
if trapped > 0 {
    water += trapped
}

When to Use This Pattern

When you see a problem asking how much water can be trapped between bars or heights, use the trapping rain water pattern with left and right max arrays to solve efficiently.

Common Mistakes

Mistake: Calculating trapped water without taking the minimum of left and right max heights
Fix: Always use min(leftMax[i], rightMax[i]) to find the limiting height for water trapping

Mistake: Not handling empty input array leading to index errors
Fix: Add a guard clause to return 0 if input array length is zero

Summary

Calculates how much water is trapped between bars of different heights after rain.

Use when you need to find total trapped water volume between elevation bars efficiently.

The key insight is that trapped water at each bar depends on the shorter tallest bar on either side minus the bar's own height.

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