108 ms, 17 lines body, explained


  • 44

    This is a Python version of my modification of dong.wang.1694's brilliant C++ solution. It sweeps from left to right. But it doesn't only keep heights of "alive buildings" in the priority queue and it doesn't remove them as soon as their building is left behind. Instead, (height, right) pairs are kept in the priority queue and they stay in there as long as there's a larger height in there, not just until their building is left behind.

    In each loop, we first check what has the smaller x-coordinate: adding the next building from the input, or removing the next building from the queue. In case of a tie, adding buildings wins, as that guarantees correctness (think about it :-). We then either add all input buildings starting at that x-coordinate or we remove all queued buildings ending at that x-coordinate or earlier (remember we keep buildings in the queue as long as they're "under the roof" of a larger actually alive building). And then, if the current maximum height in the queue differs from the last in the skyline, we add it to the skyline.

    from heapq import *
    
    class Solution:
        def getSkyline(self, LRH):
            skyline = []
            i, n = 0, len(LRH)
            liveHR = []
            while i < n or liveHR:
                if not liveHR or i < n and LRH[i][0] <= -liveHR[0][1]:
                    x = LRH[i][0]
                    while i < n and LRH[i][0] == x:
                        heappush(liveHR, (-LRH[i][2], -LRH[i][1]))
                        i += 1
                else:
                    x = -liveHR[0][1]
                    while liveHR and -liveHR[0][1] <= x:
                        heappop(liveHR)
                height = len(liveHR) and -liveHR[0][0]
                if not skyline or height != skyline[-1][1]:
                    skyline += [x, height],
            return skyline

  • 2
    T

    This is such an elegant code! Thanks for showing it!

    one comment I had is that it seems like the line:

    while i < n and LRH[i][0] == x:
    

    is not necessary. I removed it and it seems the code runs with the same efficiency. Any reason why it is kept in there?


  • 2

    Thanks, I appreciate the kind words and you looking into this so deeply :-)

    Try input [[1, 2, 1], [1, 2, 2]]. If you remove that line (and unindent the following two, of course), then the output is [[1, 1], [1, 2], [2, 0]], which is wrong. I really need to add all buildings (starting at that x) at once (or I'd need to add the tallest first, which would require special sorting, or I'd need to merge height changes).

    But you're right, the online judge doesn't notice it, as there is no test case doing this. I'll try to get one added.


  • 0
    T

    Hi Stefan, Thank you so much for the insight! I am really curious about how does one come up with codes like these. How did you discover edge case like this?


  • 3

    Lots of experience. I've been doing this for a few years :-)

    I also learned and still learn a lot by reading good solutions of others. And in this case, like I said in the text, I actually got the idea from dong.wang.1694. I pretty much just improved the implementation in C++ and then translated to Python.


  • 2

    Thanks @StefanPochmann for suggesting this missing test case. I have just added your test case.


  • 0
    S

    Why height = len(liveHR) and -liveHR[0][0]? I think "and" for two integers is always return the second integer.


  • 0

    No, when the first integer is false, it's the result of the expression and the second integer isn't even evaluated. See the docs.


  • 0
    S

    Thank you Stefan. I noticed that len(liveHR) could be zero.


  • 3
    K

    A shorter version:

    def getSkyline(self, buildings):
        events = sorted([(L, -H, R) for L, R, H in buildings] + list(set((R, 0, None) for L, R, H in buildings)))
        res, hp = [[0, 0]], [(0, float("inf"))]
        for x, negH, R in events:
            while x >= hp[0][1]: 
                heapq.heappop(hp)
            if negH: heapq.heappush(hp, (negH, R))
            if res[-1][1] + hp[0][0]: 
                res += [x, -hp[0][0]],
        return res[1:]

  • 0

    @kitt Very nice! You should post it as your own question or at least as an answer, so it's more visible and so I can upvote it :-)

    You can save three more chars by using a set comprehension for the building endings. And I tried a few more ways, shortest nice one I got is this:

    events = sorted(event for L, R, H in buildings for event in ((L, -H, R), (R, 0, None)))

  • 0
    K

    here, list(set((R, 0, None) for L, R, H in buildings)) is faster since it removes duplicates.


  • 0
    This post is deleted!

  • 0

    Yeah, I was just going for code size. And the duplicate removal costs some time, too, and I wasn't sure how it would compare. But I did some local testing now (running the OJ's cases 100 times) and yours was indeed faster (9.2 seconds vs 11.5 seconds).

    Set comprehension is not only shorter but also a bit faster, though. Ten attempts each, sorted:

    Your original:          9.14, 9.18, 9.18, 9.19, 9.19, 9.19, 9.20, 9.20, 9.22, 9.38
    With set comprehension: 9.07, 9.08, 9.09, 9.10, 9.11, 9.12, 9.15, 9.16, 9.28, 9.29

  • 0
    K

    True, my local test:

    import timeit
    >>> timeit.timeit('{i / 2 for i in range(100)}')
    8.681512117385864
    >>> timeit.timeit('set(i / 2 for i in range(100))')
    11.158149003982544
    

    Thanks for this fact!


  • 0
    J

    Great solution! Is the time complexity of this solution O(n*logn)? Because every x-coordinate is processed once: push left-x, pop right-x.("push" and "pop" operation is O(logn))


  • 0

    Yes, O(n*logn).


  • 0
    W

    really nice code!


  • 1
    O

    @StefanPochmann

    I just use 0 instead of None.

    It saves another 3 chars and makes more sense in the comparison below, or is there any special reason why None is better?

    The code looks like this:

    class Solution(object):
        def getSkyline(self, buildings):
            p = sorted(x for L,R,H in buildings for x in ((L,-H,R),(R,0,0)))
            ret, heap = [], []
            for L, negH, R in p:
                while heap and L >= heap[0][1]:
                    heapq.heappop(heap)
                heapq.heappush(heap, (negH, R))
                if not ret or ret[-1][1] != -heap[0][0]: 
                    ret.append([L, -heap[0][0]])
            return ret
    

  • 0
    A

    @StefanPochmann
    can you please add your explanation as a comment to the code.
    I understand what you said but cannot follow where in the code you are doing it
    I would reallllyyy appreciate it :)


Log in to reply
 

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