2 minutes

# Leetcode 42

I got the idea of this solution from qddpx’s solution. I thought that it was an ingenious solution, so I decided to explain it.

I think that this solution will be easier to understand if you first understand what the code is doing, so I decided to make a GIF about this.

We loop through `height`

3 different times:

- The first time we loop through
`height`

, we loop from`0`

to`len(height)`

and make each value in a new array called`lToR`

(left to right) the maximum value that we have reached so far in`height`

. - Then we can loop through
`height`

backwards from`len(height) - 1`

to`0`

. We can do the same thing except with a different array called`rToL`

(right to left). - Then, we can find the minimum of
`lToR[i]`

and`rToL[i]`

to see the maximum level that our water will fill. Then we can subtract`height[i]`

from the minimum to remove any extra water that would be in the place of`height[i]`

.

You might want to take another look at the GIF. It might make some more sense since you know what is happening.

```
func trap(height []int) int {
res := 0
lToR := make([]int, len(height))
rToL := make([]int, len(height))
max := height[0]
for i := 0; i < len(height); i++ {
if height[i] > max { max = height[i] }
lToR[i] = max
}
max = height[len(height) - 1]
for i := len(height) - 1; i >= 0; i-- {
if height[i] > max { max = height[i] }
rToL[i] = max
}
for i := 0; i < len(height); i++ {
res += int(math.Min(float64(rToL[i]), float64(lToR[i]))) - height[i]
}
return res
}
```

Read other posts