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 receive a list of buildings represented as [left, right, height]. Each building forms a rectangle on the x-axis. The task is to compute the city's skyline — the outer contour formed by these buildings — and return the critical points where the skyline height changes.
Approach 1: Sweep Line Algorithm with Priority Queue (O(n log n) time, O(n) space)
This approach treats building edges as events and processes them from left to right using a line sweep. Each building generates two events: a start edge and an end edge. Start edges add a height to a max structure, while end edges remove it. A max heap (implemented with a heap / priority queue) tracks the current tallest active building as the sweep line moves across the x-axis.
Sort all edges by x-coordinate, with start edges processed before end edges when coordinates match. As you iterate through events, update the heap and check whether the maximum height changes. Whenever the current maximum height differs from the previous height, you record a new skyline key point. The heap ensures insertion and removal operations take O(log n), and processing all building edges results in O(n log n) total time.
This method is the most widely used solution in interviews and production systems because it directly models the geometric sweep of the skyline. It also scales well for large inputs and handles overlapping buildings naturally.
Approach 2: Divide and Conquer (O(n log n) time, O(n) space)
The divide and conquer strategy mirrors the merge step used in merge sort. Split the buildings array into two halves, recursively compute the skyline for each half, then merge the two skyline outlines into one. Each skyline is a list of key points describing height transitions.
During the merge step, iterate through both skylines simultaneously. Maintain the current height from each skyline and compute the combined height as the maximum of the two. Whenever the maximum height changes, append a new key point to the merged skyline. This merge process runs in linear time relative to the number of skyline points.
Because the buildings list is repeatedly divided and merged, the total complexity becomes O(n log n) with O(n) additional memory. The algorithm demonstrates strong understanding of divide and conquer techniques and skyline merging logic.
Recommended for interviews: The sweep line approach with a priority queue is the expected solution in most interviews. It shows that you can model geometric problems with event processing and efficient data structures. The divide and conquer method is also accepted and demonstrates strong algorithmic reasoning, but the sweep line solution is more common in discussion and easier to implement under interview pressure.
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.
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.
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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sweep Line with Priority Queue | O(n log n) | O(n) | Best general solution; standard interview approach for skyline and interval sweep problems |
| Divide and Conquer | O(n log n) | O(n) | Useful when demonstrating recursive skyline merging or applying merge-sort style reasoning |
Skyline Problem • Tushar Roy - Coding Made Simple • 197,200 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