The Skyline Problem
Understanding the Problem
A city skyline viewed from far away is a silhouette: the outline traced by the tallest visible building at every horizontal position. That outline is what we compute.
Each building is a rectangle defined by its left x-coordinate, right x-coordinate, and height. The skyline consists of "key points" where the height of the silhouette changes. We record a new point only when the maximum height at that x-coordinate differs from the previous maximum height.
The complication is overlapping buildings. When buildings overlap, only the tallest one is visible. When a tall building ends but a shorter one behind it is still standing, the height drops to the shorter building's height, not to zero. So the core question reduces to: at every x-coordinate where a building starts or ends, what is the current maximum height among all buildings covering that point?
Key Constraints:
1 <= buildings.length <= 10^4-- Each building generates two events (start and end), so up to 20,000 events. An O(n^2) scan over events is on the order of hundreds of millions of operations, so O(n log n) is the target.0 <= left_i < right_i <= 2^31 - 1-- Coordinates range up to roughly 2 billion, so a coordinate-indexed array is impossible. Processing has to be event-based, driven by the building edges rather than by every integer position.1 <= height_i <= 2^31 - 1-- Heights fit in a 32-bit signed integer. We never add or multiply heights, only compare them, so there is no overflow risk here.buildings is sorted by left_i-- The input is pre-sorted by left edge. That does not remove the need to sort events, because right edges interleave with the left edges of later buildings.
Approach 1: Brute Force (Scan All Critical Points)
Intuition
The skyline height can only change at x-coordinates where a building starts or ends. Between two consecutive edges the set of covering buildings is fixed, so the height is constant there. That means we only ever have to evaluate the height at these "critical" x-coordinates.
The brute-force version collects all critical x-coordinates, sorts them, and at each one scans every building to find the maximum height of any building covering that point. It does redundant work (re-scanning all buildings at every point) but it captures the core logic directly.
Algorithm
- Collect all left and right x-coordinates from all buildings into a set (to deduplicate).
- Sort these critical x-coordinates.
- For each critical x-coordinate, scan all buildings. A building covers this x if
left <= x < right. Track the maximum height among all covering buildings. - If this maximum height differs from the previous height, add
[x, maxHeight]to the result.
Example Walkthrough
Code
- Time Complexity: O(n^2). We have at most 2n critical x-coordinates. For each one, we scan all n buildings. That gives O(n * n) = O(n^2).
- Space Complexity: O(n). The set of critical x-coordinates takes O(n) space. The result list is at most O(n) as well.
The waste is clear: at each critical x-coordinate we rescan all n buildings, even though only one building changes state from one critical point to the next. The next approach keeps a running collection of the currently active buildings and queries its maximum in O(log n) per event instead of O(n).
Approach 2: Sweep Line with Max-Heap
Intuition
Instead of re-scanning all buildings at every critical point, we process events in order along the x-axis. Each building creates two events: a "start" event at its left edge, where the building becomes active, and an "end" event at its right edge, where it becomes inactive.
Sort the events by x-coordinate and maintain an active set of building heights that supports fast maximum queries (a max-heap or an ordered multiset). Walking the events left to right, each start adds a height to the active set and each end removes one. After processing every event at a given x, the maximum of the active set is the skyline height there. Whenever that maximum differs from the previous one, we record a key point.
Ties at the same x need a defined order. To represent start events we store the height as negative and end events as positive. Sorting then breaks ties by this signed value, so at a shared x all starts (negative) come before all ends (positive).
Consider two buildings of height 3 that touch, one spanning [0, 2] and the next [2, 5]. At x = 2 the first building ends and the second starts. If we processed the end first, the active set would briefly drop to height 0, and we would emit a spurious key point [2, 0] followed by [2, 3], splitting one flat roofline into a false dip. Processing the start first keeps the maximum at 3 throughout x = 2, so no key point is emitted and the two roofs merge into one segment, which is the correct skyline.
The same ordering matters when a taller building starts exactly where a shorter one ends: handling the start first lets the new, taller height win immediately rather than recording a transient lower value.
Algorithm
- Create events: for each building
[left, right, height], add(left, -height)for start and(right, height)for end. - Sort events by x-coordinate, then by height value (negative heights sort first at same x).
- Maintain a height-count map (acting as a multiset) initialized with
{0: 1}for the ground level. - For each event:
- If it's a start event (negative height), increment the count for that height.
- If it's an end event, decrement the count (and remove if zero).
- Query the current maximum height.
- If it changed from the previous maximum, add
[x, currentMax]to the result.
Example Walkthrough
Code
- Time Complexity: O(n log n). Creating and sorting the 2n events is O(n log n). Each event does an O(log n) ordered-map or heap operation. The lazy-deletion versions (Python, Go, JavaScript, TypeScript) may leave stale entries in the heap, but every value is pushed and popped at most once, so the total heap work is still O(n log n).
- Space Complexity: O(n). The events list is O(n), and the ordered map or heap holds at most O(n) heights at a time.
The sweep line with a TreeMap already runs in O(n log n). An alternative is divide and conquer: split the buildings in half, solve each half recursively, and merge the two skylines like merge sort.
Approach 3: Divide and Conquer
Intuition
This approach follows the structure of merge sort. Split the buildings into two halves, recursively compute the skyline for each half, then merge the two skylines into one.
The merge step is where the two contours combine. We walk through both skylines at once with two pointers. As we advance, we keep leftH and rightH, the current height contributed by each side. At each new x-coordinate, the merged height is max(leftH, rightH). If that differs from the previously recorded height, we add a key point.
This is correct because each half's skyline already captures every height change for its own buildings, and the final skyline at any x is the maximum over all buildings, which equals the maximum of the two partial skylines at that x. Merging by taking the pointwise maximum (the upper envelope of the two contours) therefore produces the combined skyline.
Algorithm
- Base case: if there's only one building
[left, right, height], the skyline is[[left, height], [right, 0]]. - Split buildings into left and right halves.
- Recursively compute the skyline for each half.
- Merge the two skylines:
- Use two pointers
iandjto walk through left and right skylines. - Track
leftHeightandrightHeight(the current height from each side). - At each step, pick the point with the smaller x. Update the corresponding height tracker.
- The merged height is
max(leftHeight, rightHeight). If it differs from the previous merged height, add it.
Example Walkthrough
Code
- Time Complexity: O(n log n). The recurrence is T(n) = 2T(n/2) + O(n), where the O(n) is the merge. By the Master Theorem this resolves to O(n log n), the same as merge sort.
- Space Complexity: O(n). The recursion stack is O(log n) deep. Along any single path from root to leaf, the partial skylines held alive sum to n + n/2 + n/4 + ... = O(n), so the auxiliary space is O(n) rather than O(n log n). The output list itself is also O(n).