218. The Skyline Problem

Problem¶

Given buildings as [left, right, height], return the skyline's key points [x, height], recording only positions where the maximum visible height changes. Buildings cover half-open intervals [left, right).

Input:  [[2,9,10], [3,7,15], [5,12,12]]
Output: [[2,10], [3,15], [7,12], [12,0]]

Key trick¶

Sweep through all building edges while maintaining active buildings in a max-heap; store each building's right edge so expired buildings can be removed lazily.

Trap¶

Process every event at the same x together, or duplicate and incorrect key points may appear.
A building is inactive at its right edge because it covers [left, right).
Do not iterate over every integer coordinate: coordinates can be as large as \(2^{31}-1\).
Python has a min-heap, so negate heights to simulate a max-heap.

Why is it interesting?¶

It combines a sweep line with a heap and lazy deletion, reducing a geometric maximum-overlap problem to ordered events.

Python solution¶

import heapq


class Solution:
    def getSkyline(self, buildings: list[list[int]]) -> list[list[int]]:
        # A start event carries its negative height and right edge.
        # An end event ensures the sweep visits every possible height change.
        events = []
        for left, right, height in buildings:
            events.append((left, -height, right))
            events.append((right, 0, 0))
        events.sort()

        # Ground remains active forever.
        heap = [(0, float("inf"))]
        res = []
        i = 0

        while i < len(events):
            x = events[i][0]

            # Apply all starts at this coordinate before measuring the skyline.
            while i < len(events) and events[i][0] == x:
                _, neg_height, right = events[i]
                if neg_height:
                    heapq.heappush(heap, (neg_height, right))
                i += 1

            # Expired entries buried in the heap can remain until they reach
            # the top because only the tallest active building matters.
            while heap[0][1] <= x:
                heapq.heappop(heap)

            height = -heap[0][0]
            if not res or res[-1][1] != height:
                res.append([x, height])

        return res

Time complexity: \(O(n \log n)\).

Space complexity: \(O(n)\).

Comment on my solution¶

The first solution is logically correct, but it scans every building at every distinct edge, giving \(O(n^2)\) time in the worst case.
The second solution scans every integer coordinate, so its time and space are \(O(nR)\) and \(O(R)\), where \(R = \max(right)-\min(left)\); this is infeasible for coordinates up to \(2^{31}-1\).
In both versions, names such as left, right, and height would express the geometry more clearly than x, y, and z.
Building edges are the correct candidate coordinates; the missing optimization is maintaining active heights instead of rescanning every building.

# Ideas:
# - greedy, while on x axes take the max z on each interesecting interval
#   - create point (x, y) for each x
#   - merge (x1, z1) and (x2, z2) when x1, x2 adjacente and z1 == z2
#   - create new interval on x2, y2 if they differ
# - changes happen only on x, y coordinate

# WORKS but slow
class Solution:
    def getSkyline(self, buildings: list[list[int]]) -> list[list[int]]:
        # [[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]]
        line = []

        sides = set()
        for x, y, _ in buildings:
            sides.add(x)
            sides.add(y)

        for i in sorted(list(sides)):
            max_z = 0
            for x, y, z in buildings:
                if x > i:
                    break
                if i < y:
                    max_z = max(max_z, z)
            line.append([i, max_z])
        # merge
        points = [line[0]]
        for x, y in line:
            if y != points[-1][1]:
                points.append([x, y])
        return points

# WRONG
# Memory Limit Exceeded: 3/44 testcases passed
class Solution:
    def getSkyline(self, buildings: list[list[int]]) -> list[list[int]]:
        # [[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]]
        lo = buildings[0][0]
        hi = buildings[-1][1]
        line = []

        for i in range(lo, hi + 1):
            max_z = 0
            for x, y, z in buildings:
                if x > i:
                    break
                if i < y:
                    max_z = max(max_z, z)
            line.append([i, max_z])
        # merge
        points = [line[0]]
        for x, y in line:
            if y != points[-1][1]:
                points.append([x, y])
        return points