The Skyline Problem
Last Updated: March 28, 2026
Understanding the Problem
Imagine looking at a city skyline from far away. You see a silhouette: the outline where the tallest visible building changes. That's what we need to 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 only record a new point when the maximum height at that x-coordinate differs from the previous maximum height.
The tricky part is handling overlapping buildings. When buildings overlap, only the tallest one is visible in the skyline. When a tall building ends but a shorter one behind it is still going, the height drops to the shorter building's height, not to zero. So the core challenge is: at every x-coordinate where something interesting happens (a building starts or ends), what is the current maximum height?
Key Constraints:
1 <= buildings.length <= 10^4-- Up to 10,000 buildings. Each building generates 2 events (start and end), so we have up to 20,000 events. An O(n^2) solution with n = 20,000 gives 400 million operations, which is borderline. O(n log n) is the safe target.0 <= left_i < right_i <= 2^31 - 1-- Coordinates can be huge (up to ~2 billion), so we cannot use a coordinate-indexed array. We need event-based processing.1 <= height_i <= 2^31 - 1-- Heights can also be very large. No special constraints here, but watch for integer overflow if multiplying heights.buildings is sorted by left_i-- The input is pre-sorted by left edges, which is convenient but doesn't eliminate the need to sort events by x-coordinate (since right edges interleave with left edges).
Approach 1: Brute Force (Scan All Critical Points)
Intuition
The simplest way to think about this: the skyline height can only change at x-coordinates where a building starts or ends. So we collect all these "critical" x-coordinates, sort them, and at each one, scan every building to find the maximum height of any building covering that point.
This is brute force because for each critical point, we check every building. But it's a clean starting point that captures the essential logic.
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.
For each critical x-coordinate, we're scanning every building even though most buildings don't change between consecutive points. What if we maintained a data structure that tracks only the currently active buildings and gives us the maximum height in O(log n)?
Approach 2: Sweep Line with Max-Heap
Intuition
Instead of re-scanning all buildings at every critical point, we can process events in order. Each building creates two events: a "start" event at its left edge (a building becomes active) and an "end" event at its right edge (a building becomes inactive).
If we sort these events by x-coordinate and maintain a max-heap of active building heights, we can find the current maximum height in O(log n). Whenever the maximum height changes, we record a new key point.
The tricky detail is handling ties. When multiple events share the same x-coordinate, we need a specific processing order: process "start" events before "end" events at the same x (so we don't record a false dip). A common trick is to represent start events with negative heights. When sorted, negative values come before positive ones at the same x, which naturally processes starts before ends.
The key insight is that the skyline height only changes at building edges. By converting buildings into start/end events and processing them left to right, we simulate walking along the x-axis. The max-heap (or sorted structure) tracks which buildings are currently "active" and tells us the tallest one at any moment.
The sorting order of events handles the edge cases: when a building starts and another ends at the same x, we process the start first. This prevents recording a temporary height drop that doesn't actually exist in the skyline.
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). We create 2n events and sort them: O(n log n). Each event involves an O(log n) heap/tree operation. Total: O(n log n). Note: The Go and JavaScript implementations use linear scans for max, making them O(n^2).
- Space Complexity: O(n). The events list is O(n). The heap or tree structure holds at most n heights.
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 borrows directly from merge sort. Split the buildings into two halves, recursively compute the skyline for each half, then merge the two skylines.
The merge step is the clever part. We walk through both skylines simultaneously using two pointers. At each x-coordinate, we take the maximum of the current heights from both skylines. If this maximum differs from the previously recorded height, we add a new key point.
This works because each half's skyline correctly captures the height changes for its buildings. When we merge, we're combining two correct partial answers into the full answer by taking the "envelope" (max at every point).
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) for the merge step. By the Master Theorem, this is O(n log n), identical to merge sort.
- Space Complexity: O(n log n). The recursion depth is O(log n). At each level, the merge creates new lists totaling O(n) points. So the total space across all recursion levels is O(n log n).