One pointer solution / Divide&Conquer solution / Explanation / Python


  • 0

    For every "temp highest bar" so far, we suppose there exists a bar that is higher, and we can add water without worrying, until we find a bar there is no bar higher in the future, we reverse the rest of the array and add water again

    The solution is actually very similar to two-pointer solution

    class Solution(object):
        def trap(self, height):  # one pointer solution
            if len(height)<=2:
                    return 0
            def one_pass_to_last_high(height):
                temp_max, temp_water, water_total, last_id = 0,0,0,0
                for i, h in enumerate(height):
                    if h>=temp_max:
                        water_total+=temp_water
                        last_id, temp_max, temp_water = i, h, 0
                    else:
                        temp_water+=(temp_max-h)
                return last_id, water_total
    
            last_id, total_water = one_pass_to_last_high(height)
            return total_water+one_pass_to_last_high(height[last_id:][::-1])[1]
            
    

    Divide&Conquer is much more easier to understand, the highest bar and the second highest bar can always form a "bowl" and contain water if they have distance in x-axis, then we divide until there is no "bowl" at all

    class Solution(object):
        def trap(self, height):   # dc solution
            """
            :type height: List[int]
            :rtype: int
            """
            
            if len(height)<=2:
                return 0
            
            # find indices of the top2 highest bar
            max_1 = max_2 = float('-inf')
            idx1 = idx2 = len(height)
            for i, h in enumerate(height):
                if h>max_2:
                    if h>max_1:
                        max_1, max_2, idx1, idx2 = h, max_1, i, idx1
                    else:
                        max_2, idx2 = h, i
            if idx1>idx2:
                idx1, idx2 = idx2, idx1
            # finish finding
                
            return self.one_bowl(height[idx1:idx2+1])+self.trap(height[:idx1+1])+self.trap(height[idx2:])
                
        def one_bowl(self, heights): 
            h_min, water_sum = min(heights[0], heights[-1]), 0
            for h in heights[1:-1]:
                water_sum+=(h_min-h)
            return water_sum
    

Log in to reply
 

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