Golang easy to understand 2 pass solution


  • 0

    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
    }
    

Log in to reply
 

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