# Golang easy to understand 2 pass solution

• The fact we need to realize is that, for `height[i]`, amount of water to be filled in can be determined by the smaller amount between "highest left height" and "highest right height".

``````■
■ ■     ■
■ ■ ■   ■
0 1 2 3 4
``````

See the example above. Amount of water of `3` th index is `2`, because highest right side = `2` (index `4`) and left side = `3` (index `0`), and the height of self = `0`, thus `2 - 0 = 2`.
Amount of water of `2` nd index = `1` because highest right side = `2` (index `4`) and left side = `3` (index `0`) and self = `1`, thus `2 - 1 = 1`.

So first we iterate through the height array and record for each index, what is the highest left value and right value (excluding itself). After that iteration, we again iterate through `[0:len(height)]` and pick smaller one between the highest left and highest right, then add the amount it as a result. Of course, however, if the height of `i` th index is taller than the highest left or right, no water can be filled in.

``````func trap(height []int) int {
hlen := len(height)
if hlen < 3 {
return 0
}
highestLeft, highestRight := make([]int, hlen), make([]int, hlen)

highestLeft[0], highestRight[hlen-1] = 0, 0 // i= 0
highestLeft[1], highestRight[hlen-2] = height[0], height[hlen-1] // i = 1
maxl, maxr := height[0], height[hlen-1]

for i := 2; i < hlen; i++ {
j := hlen - i - 1
maxl, maxr = max(height[i-1], maxl), max(height[j+1], maxr)
highestLeft[i], highestRight[j] = maxl, maxr
}

water := 0
for i := 0; i < hlen; i++ {
if highestLeft[i] > highestRight[i] {
water += max(highestRight[i] - height[i], 0)
} else if highestLeft[i] <= highestRight[i] {
water += max(highestLeft[i] - height[i], 0)
}
}
return water
}

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.