My 220ms divide and conquer solution in Python O(nlogn)


  • 9
    H
    class Solution:
        # @param {integer[][]} buildings
        # @return {integer[][]}
        def getSkyline(self, buildings):
            if buildings==[]:
                return []
            if len(buildings)==1:
                return [[buildings[0][0],buildings[0][2]],[buildings[0][1],0]]
            mid=(len(buildings)-1)/2
            left=self.getSkyline(buildings[0:mid+1])
            right=self.getSkyline(buildings[mid+1:])
            return self.merge(left,right)
        def merge(self,left,right):
            i=0
            j=0
            result=[]
            h1=None
            h2=None
            while i<len(left) and j<len(right):
                if left[i][0]<right[j][0]:
                    h1=left[i][1]
                    new=[left[i][0],max(h1,h2)]
                    if result==[] or result[-1][1]!=new[1]:
                        result.append(new)
                    i+=1
                elif left[i][0]>right[j][0]:
                    h2=right[j][1]
                    new=[right[j][0],max(h1,h2)]
                    if result==[] or result[-1][1]!=new[1]:
                        result.append(new)
                    j+=1
                else:
                    h1=left[i][1]
                    h2=right[j][1]
                    new=[right[j][0],max(h1,h2)]
                    if result==[] or result[-1][1]!=new[1]:
                        result.append([right[j][0],max(h1,h2)])
                    i+=1
                    j+=1
            while i<len(left):
                if result==[] or result[-1][1]!=left[i][1]:
                    result.append(left[i][:])
                i+=1
            while j<len(right):
                if result==[] or result[-1][1]!=right[j][1]:
                    result.append(right[j][:])
                j+=1
                
            return result
    

    seems nobody use this divide and conquer solution till now, the most tricky part is:

    when we do the merge,we maintain two heights :h1 and h2. when we need to choose one element from left part, we update h1,and when we need to choose one element from right part, we update h2, the height we insert is always max(h1,h2).


  • 0
    H

    Nice Code and explain!


  • 0
    H

    I optimize your algorithm, which costs 156 ms! Here is the solution

    class Solution:
    # @param {integer[][]} buildings
    # @return {integer[][]}
    def getSkyline(self, buildings):
        n = len(buildings)
        if n == 0:
            return []
        if n == 1:
            return [[buildings[0][0],buildings[0][2]], [buildings[0][1],0]]
        mid = (n + 1)/2
        left = self.getSkyline(buildings[:mid])
        right = self.getSkyline(buildings[mid:])
        m = len(left)
        n = len(right)
        i = 0
        j = 0
        h1 , h2 = -1, -1
        result = []
        while i < m and j < n:
            if left[i][0] < right[j][0]:
                h1 = left[i][1]
                tmp = [left[i][0], h1] if h1 >= h2 else [left[i][0], h2]
                if result == [] or result[-1][1] != tmp[1]:
                    result.append(tmp)
                i += 1
            elif left[i][0] > right[j][0] :
                h2 = right[j][1]
                tmp = [right[j][0], h2] if h2 >= h1 else [right[j][0], h1]
                if result == [] or result[-1][1] != tmp[1]:
                    result.append(tmp)
                j += 1
            else:
                h1=left[i][1]
                h2=right[j][1]
                tmp =[right[j][0], h2] if h2 >= h1 else [right[j][0], h1]
                if result==[] or result[-1][1]!=tmp[1]:
                    result.append(tmp)
                i+=1
                j+=1
        while i < m:
            if result==[] or result[-1][1]!=left[i][1]:
                result.append(left[i][:])
            i+=1
        while j < n:    
            if result==[] or result[-1][1]!=right[j][1]:
                result.append(right[j][:])
            j+=1
        return result 

  • 0

    Great solution, simple but clever. Kudos. +1


  • 0
    S

    Here is my code inspired by your idea - accepted in 145 ms

    class Solution(object):
        def getSkyline(self, buildings):
            """
            :type buildings: List[List[int]]
            :rtype: List[List[int]]
            """
            if len(buildings) == 0:
                return [ ]
            
            if len(buildings) == 1:
                return [ [ buildings[0][0], buildings[0][2]], [buildings[0][1], 0] ]
            
            mid   = len(buildings)//2
            left  = self.getSkyline(buildings[:mid])
            right = self.getSkyline(buildings[mid:])
    
            return self.merge(left,right)
        
        def merge(self,left,right):
            output  = [[0,0]]
            i,j,m,n = 0,0,len(left),len(right)
            ly,ry   = -1,-1
            ansx    = -1
            ansy    = -1
            while i < m and j < n:
                ansx = -1
                ansy = -1
                if left[i][0] < right[j][0]:
                    ly   = left[i][1]
                    ansx = left[i][0]
                    ansy = max(ly,ry)
                    i   += 1
                elif left[i][0] > right[j][0]:
                    ry = right[j][1]
                    ansx = right[j][0]
                    ansy = max(ly,ry)
                    j += 1
                elif left[i][0] == right[j][0]:
                    ly = left[i][1]
                    ry = right[j][1]
                    ansx = left[i][0]
                    ansy = max(ly,ry)
                    i += 1
                    j += 1
                # ansx - the one that comes first in x-axis
                # ansy - the tallest height that is 'overshadowing' current point
                if ansx != -1 and output[-1][1] != ansy:
                    # if the taller point is already dominating, the ansx will not appear in silhouette
                    output.append( [ ansx, ansy] )
    
            while i < m:
                output.append( left[i][:] )
                i += 1
    
            while j < n:
                output.append( right[j][:])
                j += 1
            return output[1:]
    

  • 0

    Nice solution!
    Divide and merge is much easier to code than using heap.
    A shorter version

    class Solution(object):
        def getSkyline(self, blds):
            """
            :type blds: List[List[int]]
            :rtype: List[List[int]]
            """
            if not blds: return []
            if len(blds) == 1: return [[blds[0][0], blds[0][2]], [blds[0][1], 0]]
            mid = len(blds) // 2
            left = self.getSkyline(blds[:mid])
            right = self.getSkyline(blds[mid:])
            return self.merge(left, right)
        
        def merge(self, left, right):
            h1, h2, res = 0, 0, []
            while left and right:
                if left[0][0] < right[0][0]:
                    pos, h1 = left[0]
                    left = left[1:]
                elif left[0][0] > right[0][0]:
                    pos, h2 = right[0]
                    right = right[1:]
                else:
                    pos, h1 = left[0]
                    h2 = right[0][1]
                    left = left[1:]
                    right = right[1:]
                H = max(h1, h2)
                if not res or H != res[-1][1]:
                    res.append([pos, H])
            if left:
                res += left
            if right:
                res += right
            return res
    

Log in to reply
 

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