Python program to solve the "skyline problem"

Question

This is a Leetcode problem -

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]].

The output is a list of "key points" (red dots in Figure B) in the format of [[x1,y1], [x2, y2], [x3, y3], ...] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as: [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]].

Notes -

The number of buildings in any input list is guaranteed to be in the range [0, 10000].

The input list is already sorted in ascending order by the left x position Li.

The output list must be sorted by the x position.

There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...].

Here is my solution to this task using divide and conquer (in Python) -

   class Solution:
         def get_skyline(self, buildings):
             """
             :type buildings: List[List[int]]
             :rtype: List[List[int]]
             """
             if not buildings:
                 return []
             if len(buildings) == 1:
                 return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]]

             mid = len(buildings) // 2
             left = self.get_skyline(buildings[:mid])
             right = self.get_skyline(buildings[mid:])
             return self.merge(left, right)

         def merge(self, left, right):
             h1, h2 = 0, 0
             i, j = 0, 0
             result = []

             while i < len(left) and j < len(right):
                 if left[i][0] < right[j][0]:
                     h1 = left[i][1]
                     corner = left[i][0]
                     i += 1
                 elif right[j][0] < left[i][0]:
                     h2 = right[j][1]
                     corner = right[j][0]
                     j += 1
                 else:
                     h1 = left[i][1]
                     h2 = right[j][1]
                     corner = right[j][0]
                     i += 1
                     j += 1
                 if self.is_valid(result, max(h1, h2)):
                     result.append([corner, max(h1, h2)])
             result.extend(right[j:])
             result.extend(left[i:])
             return result

         def is_valid(self, result, new_height):
             return not result or result[-1][1] != new_height

Here is an example output -

#output = Solution()
#print(output.get_skyline([[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]))

>>> [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]

Here is the time taken for this output -

%timeit output.get_skyline([[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]])
>>> 27.6 µs ± 3.65 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

So, I would like to know whether I could make this program more efficient and/or shorter. Any alternatives are welcome.

Answer 1

Nice approach.

It's quite a hard problem to analyse for running time, because the output size is variable. merge has running time linear in the total size of its inputs, which are the output sizes of the subproblems. What we can say is that the base case produces two points for one input point, and merge doesn't create new points, so the number of points merged is at most twice the number of input points. Therefore the recurrence is \$T(n) = 2T(n/2) + O(n)\$ which is the standard recurrence giving \$O(n \lg n)\$.

We can also show that this can't be beaten by a reduction from sorting. Given a set \$\{x_i\}\$ to sort, we find the maximum \$m\$ and construct buildings \$\{(0, m + 1 - x_i, x_i)\}\$. The output will give the \$x_i\$ sorted in descending order.

So your approach is asymptotically optimal, and moreover elegant. The merge doesn't do anything fancy, so it should have a low constant hidden by the big-O notation.

---

I think that some of the double-indexed array accesses could benefit from introducing names. In particular, I would find

            return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]]

much more readable as

            l, r, h = buildings[0]
            return [[l, h], [r, 0]]

---

The three cases in merge can be simplified considerably by using <=. I find is_valid inelegant, so I would eliminate it by keeping track of the "current" height. Introducing names for left[i][0] and right[j][0] I refactored your code to

    def merge(self, left, right):
        h1, h2, hcurrent = 0, 0, 0
        i, j = 0, 0
        result = []

        while i < len(left) and j < len(right):
          x0 = left[i][0]
          x1 = right[j][0]
            if x0 <= x1:
                h1 = left[i][1]
                i += 1
            if x1 <= x0:
                h2 = right[j][1]
                j += 1
            if max(h1, h2) != hcurrent:
                hcurrent = max(h1, h2)
                result.append([min(x0, x1), hcurrent])
        result.extend(right[j:])
        result.extend(left[i:])
        return result

It could alternatively be refactored to use a sentinel as so:

    def merge(self, left, right):
        h1, h2 = 0, 0
        i, j = 0, 0
        result = [[0, 0]]

        while i < len(left) and j < len(right):
            x0 = left[i][0]
            x1 = right[j][0]
            if x0 <= x1:
                h1 = left[i][1]
                i += 1
            if x1 <= x0:
                h2 = right[j][1]
                j += 1
            if max(h1, h2) != result[-1][1]:
                result.append([min(x0, x1), max(h1, h2)])
        result.extend(right[j:])
        result.extend(left[i:])
        return result[1:]

Either way, I think it would be good to add a comment explaining why

        result.extend(right[j:])
        result.extend(left[i:])

doesn't need any extra checks to avoid producing two consecutive points at the same height.

Answer 2

In addition to the existing great answer of Peter Taylor I would like to add some thoughts on methods vs. free functions.

Python is a multiparadigm language. It is concentrated on, but not only about object oriented programming. It is certainly possible to construct one large Solution class that contains all your methods, but it might be not the best Solution. (höhö)

As a general guideline you can use classes to group data and functions acting on that data together. If you simply want to group functions together into one namespace, you should use namespaces i.e. modules in python.

Let's get concrete and have a look at your is_valid method. It never uses self. If you want to keep the class structure, you should make this at least explicit and change it to:

@staticmethod
def is_valid(result, new_height):

A staticmethod is basically a free function residing in the namespace of a class.

But (opinionated) it might be even better in terms of reusability to completely "free" your function. If you come from a C++ background this makes it feel like a template function that you can apply on different inputs independent of the Solution class.

If you "freed" is_valid you will realize, that merge does not depend on self either and if you "freed" merge you will finally realize that get_skyline is basically a recursive function that calls merge and can be a staticmethod or a free function itself.

In the end you end up with a class of three staticmethods i.e. a namespace with three free functions. The canonical way of implementing this structure is to have those three function in their own module i.e. their own file.

Practically speaking, just delete the class and references to self, dedent the methods and call your file Solutions.py. Then you will be able to call

import Solutions
Solutions.get_skyline(my_cool_skyline_test_data)

which feels very similar in terms of syntax as your class approach but decoupled the functions from each other.

If you think that a function like is_valid is an implementation detail of your module, you can prepend an underscore which makes it private by convention. This would allow to switch between an _is_valid function and the manual "current" height tracking suggested in the other answer.