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
}
```