Trapping Rain Water

1. Problem Description

Given n non-negative integers representing an elevation map where each bar has width 1, calculate how much rain water can be trapped after raining.

2. Approach

1. Two pointers
   • For each element, scan left to find the maximum value and scan right to find the maximum value
   • Take the smaller of the two maxima and subtract the current height to get the maximum water that can be trapped at this position
   • Sum the values

3. Implementation

3.1. Two Pointers (Expand from the Center)

func trap(height []int) int {
    res := 0
    for i := 0; i < len(height); i++ {
        maxLeft := height[i]
        for left := i; left >= 0; left--{
            maxLeft = max(maxLeft, height[left])
        }
        maxRight := height[i]
        for right := i; right < len(height); right++{
            maxRight = max(maxRight, height[right])
        }
        res += min(maxLeft,maxRight)-height[i]
    }
    return res
}

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

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

4. References

• Trapping Rain Water - LeetCode