Two pass but very easy to understand and implement.


  • 0
    M

    This is two pass solution. In first pass, we look at the first pole and then find the immediate next pole which is greater than equal to current height. We are maintaining an array which keeps track of the water at each index. This array is updated for all ther poles in between the current pole and next taller or equal pole with the water content.
    We repeat the same process while traversing from end of the array to start.
    Then we take the max out of these two arrays at each index and sum them. This is the answer to question.

    class Solution(object):
        def trap(self, height):
            if len(height) < 3: return 0
            i, sm_ar,sm, h = 0, [], 0, height
            fwd, bckd = [0]*len(h),[0]*len(h)
    
            #find first pole with height greater than 0
            while i < len(h):
                if h[i] != 0: break
                i+=1
            #moving one line ahead to get the next pole.
            prev = i
            i += 1
            while i < len(h):
                if h[i] >= h[prev]:
                    for j in range(prev+1,i):
                        fwd[j] = h[prev] - h[j]
                    prev = i
                i+=1
            
            j = len(h) - 1
            while j > -1:
                if h[j] != 0: break
                j-=1
            prev = j
            j -= 1
            while j > -1:
                if h[j] >= h[prev]:
                    for i in range(prev-1,j, -1):
                        bckd[i] = h[prev] - h[i]
                    prev = j
                j-=1
            return sum([max(bckd[i], fwd[i]) for i in range(len(h))])
    

Log in to reply
 

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