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

• ``````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).

• Nice Code and explain!

• 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 ``````

• Great solution, simple but clever. Kudos. +1

• 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:]
``````

• 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
``````

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