168 ms, 19 lines body

  • 1

    O(n log n) time, O(n) space. But it's likely even faster than that. The log(n) only comes from:

    1. The sorted call: Python's dictionary keys can be largely sorted already (depends on the input). And Python uses Timsort, which can detect that and take advantage of it.
    2. Pushing to and popping from the heap. This is not log(n) but only log(current size of the heap).

    The code:

    from heapq import *
    from collections import *
    class Solution:
        def getSkyline(self, buildings):
            changes = defaultdict(list)
            for l, r, h in buildings:
                changes[l] += [-h]
                changes[r] += [h]
            heights, height_ctr = [0], Counter([0])
            skyline = []
            for x, changes in sorted(changes.items()):
                for h in changes:
                    if h < 0:
                        heappush(heights, h)
                        height_ctr[h] += 1
                        height_ctr[-h] -= 1
                while not height_ctr[heights[0]]:
                height = -heights[0]
                if not skyline or height != skyline[-1][1]:
                    skyline += [[x, height]]
            return skyline

Log in to reply

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