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] = [lefti, righti, heighti]:
lefti is the x coordinate of the left edge of the ith building.righti is the x coordinate of the right edge of the ith building.heighti is the height of the ith 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 except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.
Note: There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3],[4 5],[7 5],[11 5],[12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...,[2 3],[4 5],[12 7],...]
Example 1:
Input: 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]] Explanation: Figure A shows the buildings of the input. Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.
Example 2:
Input: buildings = [[0,2,3],[2,5,3]] Output: [[0,3],[5,0]]
Constraints:
1 <= buildings.length <= 1040 <= lefti < righti <= 231 - 11 <= heighti <= 231 - 1buildings is sorted by lefti in non-decreasing order.Problem Overview: You are given a list of buildings represented as [left, right, height]. Each building forms a rectangle on the skyline. The task is to compute the outer contour of all buildings combined and return the key points where the skyline height changes.
Approach 1: Sweep Line Algorithm with Priority Queue (O(n log n) time, O(n) space)
The most common solution treats building edges as events and processes them from left to right using a sweep line. Convert every building into two events: a start edge (height enters) and an end edge (height leaves). Sort all events by x-coordinate, then track active building heights with a max heap (priority queue). When the sweep line encounters a start edge, push the height into the heap; when it encounters an end edge, remove that height. The maximum value in the heap represents the current skyline height. Whenever this maximum changes, record a new key point. The heap ensures efficient retrieval of the tallest active building in O(log n). This approach is the standard solution for skyline and interval-overlay problems and heavily relies on techniques from Line Sweep and Heap (Priority Queue).
Approach 2: Divide and Conquer (O(n log n) time, O(n) space)
This method mirrors merge sort. Split the buildings array into two halves, recursively compute the skyline for each half, then merge the two skylines into a combined outline. During merging, iterate through both skyline lists while tracking the current heights from the left and right halves. The visible skyline at any x-coordinate is the maximum of the two heights. Whenever this maximum changes, append a new key point. The key challenge is merging two skyline outlines while eliminating redundant height segments. The recursive structure leads to O(n log n) time, similar to merge sort. This approach highlights algorithmic design patterns from Divide and Conquer and is useful when reasoning about skyline merging rather than event simulation.
Recommended for interviews: The sweep line with a priority queue is the approach most interviewers expect. It demonstrates understanding of event processing, heaps, and geometric interval problems. The divide and conquer solution is equally optimal but less commonly implemented under time pressure. Showing the sweep line idea first proves you recognize the canonical skyline technique.
The Sweep Line algorithm involves moving a vertical line from left to right over the x-coordinates and maintaining a list of currently active buildings using a max-heap. The priority queue helps keep track of the tallest building at each point. As the line reaches the start of a new building, add it to the heap, and as it reaches the end of a building, remove it. The key points are detected based on changes in the maximum height at points where buildings start or end.
This code uses a priority queue (min-heap) where we push the negative of the height to simulate a max-heap, to manage the building heights efficiently. We handle start and end events separately, ensuring the heap accurately reflects the current tallest building. While processing each event, code also manages to merge the same consecutive heights, ensuring result compliance with the rules.
Python
Java
C++
C#
JavaScript
Time Complexity: O(N log N), where N is the number of events (two for each building).
Space Complexity: O(N), as we store up to N building heights in the heap.
This approach involves breaking down the problem using the divide and conquer strategy. The buildings array is split into two halves recursively. The base case is a single building, where the skyline can directly be calculated. The results are then merged, taking care of overlapping heights and ensuring continuity and distinct key points.
This Python code uses the divide and conquer strategy where each call splits the building list into two halves and recursively solves for both sides, merging their results into a coherent skyline outline by comparing the heights at each step and ensuring the output is minimal.
Python
Java
C++
C#
JavaScript
Time Complexity: O(N log N), due to division of buildings and merging.
Space Complexity: O(N), needing space for recursive stack and individual skyline lists.
| Approach | Complexity |
|---|---|
| Approach 1: Sweep Line Algorithm with Priority Queue | Time Complexity: O(N log N), where N is the number of events (two for each building). |
| Approach 2: Divide and Conquer | Time Complexity: O(N log N), due to division of buildings and merging. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sweep Line with Priority Queue | O(n log n) | O(n) | Best general solution. Efficient for large building sets and the most common interview approach. |
| Divide and Conquer | O(n log n) | O(n) | Useful when modeling the skyline merge process or applying merge-sort style recursion. |
Find the Skyline Problem with C++ Solution Explained • mCoding • 55,105 views views
Watch 9 more video solutions →Practice The Skyline Problem with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor