Trapping Rain Water | DSA Journal

Question

Given an array of non-negative integers where each element represents the height of a bar, compute how much water it can trap after raining.

Water can only be trapped between bars, and it's limited by the height of the shortest bar on either side.

Example

Input: [0, 3, 1, 4, 0, 2, 1, 5, 0, 2, 3]

Output: 15

Explanation: Water is trapped at indices 2 (2), 4 (4), 5 (2), 6 (3), 8 (3), and 9 (1). Total = 2 + 4 + 2 + 3 + 3 + 1 = 15.

Input: [1, 0, 1]

Output: 1

Explanation: 1 unit is trapped at index 1.

Visual

My Notes

Use two auxiliary arrays: one for left max, one for right max.
At each index, water trapped = min(left max, right max) - height.
If the result is positive, add it to total.
This is a dynamic programming approach.
Time complexity: O(n), Space complexity: O(n)

package main

import (
    "fmt"
)

func main() {
    result := trap([]int{0, 3, 1, 4, 0, 2, 1, 5, 0, 2, 3})
    fmt.Println(result)
}

func trap(height []int) int {
    if len(height) < 3 {
        return 0
    }

    left, right, result := make([]int, len(height)), make([]int, len(height)), 0

    left[0] = 0
    for i := 1; i < len(height); i++ {
        if left[i-1] > height[i-1] {
            left[i] = left[i-1]
        } else {
            left[i] = height[i-1]
        }
    }

    right[len(height) - 1] = 0
    for i := len(height) - 2 ; i >= 0; i-- {
        if right[i+1] > height[i+1] {
            right[i] = right[i+1]
        } else {
            right[i] = height[i+1]
        }
    }

    for i := 0; i < len(height); i++ {
        var min int

        if left[i] < right[i] {
            min = left[i]
        } else {
            min = right[i]
        }

        area := min - height[i]

        if area > 0 {
            result += area
        }
    }

    return result
}