The Skyline Problem

The Skyline Problem hard

Description

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array buildings where buildings[i] = [left_i, right_i, height_i]:

left_i is the x-coordinate of the left edge of the i-th building.
right_i is the x-coordinate of the right edge of the i-th building.
height_i is the height of the i-th building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of “key points” sorted by their x-coordinate in the form [[x1, y1], [x2, y2], ...]. Each key point is the left endpoint of some horizontal segment in the skyline. The last point in the list should have a y-coordinate of 0.

There must be no consecutive horizontal lines of equal height in the output skyline.

Examples

> Case 1:
    buildings = [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]
    Output: [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]

Constraints

1 <= buildings.length <= 10^4
0 <= left_i < right_i <= 2 × 10^9
1 <= height_i <= 10^4
Buildings are given sorted by left_i.

The D&C insight

The skyline of two buildings can be computed by:

Splitting the input into two halves.
Recursively computing each half’s skyline.
Merging the two skylines.

The merge is the heart of the algorithm: walk through both skylines simultaneously, maintaining current heights h1 and h2, and emit a new keypoint whenever max(h1, h2) changes.

Recurrence: T(n) = 2 T(n / 2) + O(n) → O(n log n).

Code

The merge step’s invariant: at any moment, h1 is the most-recent height contributed by the left skyline at the current x-cursor, and h2 is the most-recent for the right. The current emitted skyline height is max(h1, h2). When either changes (because we just consumed a keypoint from one side), we check if the new max differs from the last emitted height — if so, emit a new keypoint.

This is exactly the merge-step pattern from merge sort, generalized from “pick the smaller front element” to “track the current max contribution from each side.”

C++ / Java

Alternative — sweep line with a max-heap

The “production” answer to this problem uses an event-based sweep with a max-heap of active building heights. O(n log n) time, same asymptotic, but easier to implement correctly under time pressure. The D&C version is the textbook one and is often the version tested in algorithm courses.

Analysis

Time: O(n log n).
Space: O(n) for the recursion and intermediate skylines.

Same skin

Rectangle Area II (compute the area of the union of axis-aligned rectangles) — different sweep, related “merge outlines” feel.
Merge K Sorted Lists — same D&C merge shape applied to lists.
Closest Pair of Points — D&C with a clever merge step.
Find Intersection of Two Sorted Lists — two-pointer merge.

The skyline problem is the canonical “D&C with a non-trivial merge step” interview problem. It tests whether you understand that the merge in merge sort is the abstraction, not the concrete operation — once you grasp that, you can adapt the pattern to any problem with a “combine two ordered things” feel.

Median of Two Sorted Arrays Overview