The Skyline Problem

Hey All,

I know that I’ve told that I will work more on DP tasks, however I’ve met this one. This was probably the first time I got no idea how to solve current task. And I would say even more — even reading solutions available on Leetcode i didn’t get a clue how to solve this task.

Basically, my first decision was to build quick height map, where each element in the row will have highest height of the building. Then I just need to go through each cell, and if previous cell and current cell are different — that means that I need to save this cell.

Easy! Complexity O(n), but memory required equals = O(max(n)), where max(n) is a maximum value of n in array.

So, I ran this solution on couple of tests set and it worked! Amazing!

However simple test case: [[0,2147483647,2147483647]] brought to me memory error. And it is obvious, since in my solution my first step is to find biggest number in end coordinates of the buildings, and then create array with amount of elements equals to this max. Sorry, but 2³² is too much for my simple Mac. :) But I am sure that my solution will work on some distributed systems with very slight updates:)

Ok. So, we can’t to this straight forward solution, which forced me to read almost all topics at the Leetcode. And I will be honest — it didn’t help at all. However, I found this guy on Youtube who helped me to understand this solution at last. Anyway, if once somebody ask me this question — I would probably fail:)

Ok, let’s think about solution, and what steps we need to take to solve it.

1. Once we found that building start and it’s height is largest — that will be our skyline point.
2. Once we find building end — we need to remove building from the list. However, if this point is highest on current step -it will be skyline point as well.
3. If the building is behind more taller buildings — we should not add any skyline point.

To accomplish this, we need to:

1. Sort all buildings by their left position ( thank you leetcode, you already did this )
2. Save building endings.
3. Sort everything.
4. Once we meet new building, we need to add it’s heigh to priority queue. If in this case height is changing — that means overall max height is changing — which means that we’ve met our skyline point.

So, let’s do the first steps:

In this short code what we’ve achieved ihere

1. We receiving all building coordinates, start and end in sorted order. We can find difference between start and end, by checking if this coordinate have [2] element. As you can see, i am using negative value of height, because in Python 2, priority queue does not have method for getMax, and can return only minimum value:)
2. res and hp are two arrays. res will contain our skyline points, hp will become container for our priority queue.

Basically if our input will have next format: [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]], after first line we will transform it into array of the next format:

[(2, -10, 9), (3, -15, 7), (5, -12, 12), (7, 0, None), (9, 0, None), (12, 0, None), (15, -10, 20), (19, -8, 24), (20, 0, None), (24, 0, None)]

As you can see now it is very easy to get start and end of the buildings in sorted order.

Let’s go line-by-line for this solution:

We are going through each element in our events list

Line 2- 3 In case we found position ( it can be start or end of the building ) of our element is bigger then RIGHT position of the building in priority queue — we should remove element from the of priority queue.

Line 4–5. In case building have height — add it to priority queue.

Line 6–7. In case last added element height is different from height of fir building in priority queue ( it means that height changed ) = add new point as skyline point.

Done.

From my point of view — this solution is quite horrible for any kind of interview, since in case you do not know exact algorithm — it is almost impossible to solve it.

Analysis: complexity O(n), memory O(n).

Happy coding, Erevan!