# Recursively Merging Skylines

• Although there exists an O(n2) solution, I will be describing the O(nlogn) solution here which uses recursion.

The basic idea is to think in terms of skylines instead of buildings. So a single building of the form: `[2,9,10]` is actually a skyline of the form: `[ [2,9] , [10,0] ]`. Now we just need to think of a way to merge two skylines, which will allow us to recursively merge all our skylines together!

CONVERT TO SKYLINES

To begin, let's convert the buildings to skyline form so we don't have to juggle two data structures:

``````skylines = []
for b in buildings:   # b = [Li, Ri, Hi]
skylines.append([[b[0], b[2]],[b[1], 0]])   # [ [Li,Hi] , [Ri,0] ]
``````

MERGE SKYLINES

It's easier to introduce a new function, `mergeSkylines(skylines)` instead of dealing with the method we're given. This method takes a list of skylines, and returns a single skyline.

``````def mergeSkylines(skylines):
...
...
return skyline
``````

FIRST BASE CASE

With usual recursion, we need a base case(s). In this case, we'll have two. The
first is having 1 skyline in our list. If that happens, we just return it.

``````if len(skylines) == 1:  # A single skyline is 'already merged'
return skylines[0]
``````

SECOND BASE CASE

The second base case is when we have exactly two skylines. Merging them will require a bit of work. The code may seem intimidating, but there's a simple idea behind it. First we need to notice that a skyline will have an ascending `x` order:

``````skyline = [[5, 12], [12, 0], [15, 10], [20, 8], [24, 0]]
``````

Let's say we want to merge these two skylines:

``````skyline_l = [[2, 10], [9, 0]]
skyline_r = [[3, 15], [7, 0]]
``````

We need to keep track of each skyline's height independently. The highest of either skyline will always be the resulting height. If the building is in the back, we'll see it. If it's in the front, we'll see. So max height always wins. That's the first trick.

The second trick is to go through each point in `skyline_l` and `skyline_r` in order. And use that skyline's `x` value along with the highest `y` value from EITHER skyline.

``````yl = 0
yr = 0
x = 0
full_skyline = []

while len(l_skyline) > 0 or len(r_skyline) > 0:

xl = l_skyline[0]
xr = r_skyline[0]

if xl < xr:
p = l_skyline.pop(0)
x = p[0]
yl = p[1]

else:
p = r_skyline.pop(0)
x = p[0]
yr = p[1]

full_skyline.append([x,max(yl,yr)])
``````

Ops, what if one skylines ends?? We can catch that, and just add all the points from the non-empty skyline to our merged list. So the fixed code will look like:

``````while len(l_skyline) > 0 or len(r_skyline) > 0:

if len(l_skyline) == 0:
full_skyline.extend(r_skyline)
break

if len(r_skyline) == 0:
full_skyline.extend(l_skyline)
break

xl = l_skyline[0]
xr = r_skyline[0]

if xl < xr:
p = l_skyline.pop(0)
x = p[0]
yl = p[1]

else:
p = r_skyline.pop(0)
x = p[0]
yr = p[1]

full_skyline.append([x,max(yl,yr)])
``````

But wait, this might introduce successive points with the same height! We can fix that by going through our merged skyline and only keeping points that have a different height from the one before it:

``````fixed_full_skyline = [full_skyline[0]]

for p in full_skyline:
if p[1] != fixed_full_skyline[-1][1]:
fixed_full_skyline.append(p)
``````

MERGE STEP

Ok that was a lot ... luckily the merge step is much simpler. Just merge the left and right halves of our skylines list. Then merge the resulting two skylines:

``````skyline_1 = mergeSkylines( skylines[:num/2] )
skyline_2 = mergeSkylines( skylines[num/2:] )
return mergeSkylines([ skyline_1, skyline_2 ])
``````

Putting everything together, our solution will look like:

``````def getSkyline(buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""

# Convert single building into skyline
skylines = []
for b in buildings:
skylines.append([[b[0], b[2]],[b[1], 0]])

return mergeSkylines(skylines)

def mergeSkylines(skylines):

num = len(skylines)

if num == 1:
return skylines[0]

if num == 2:
l_skyline = skylines[0]
r_skyline = skylines[1]

yl = 0
yr = 0
x = 0
full_skyline = []

while len(l_skyline) > 0 or len(r_skyline) > 0:

if len(l_skyline) == 0:
full_skyline.extend(r_skyline)
break

if len(r_skyline) == 0:
full_skyline.extend(l_skyline)
break

xl = l_skyline[0]
xr = r_skyline[0]

if xl < xr:
p = l_skyline.pop(0)
x = p[0]
yl = p[1]

else:
p = r_skyline.pop(0)
x = p[0]
yr = p[1]

full_skyline.append([x,max(yl,yr)])

fixed_full_skyline = [full_skyline[0]]

for p in full_skyline:
if p[1] != fixed_full_skyline[-1][1]:
fixed_full_skyline.append(p)

return fixed_full_skyline

skyline_1 = mergeSkylines( skylines[:num/2] )
skyline_2 = mergeSkylines( skylines[num/2:] )
return mergeSkylines([ skyline_1, skyline_2 ])
``````

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