Watch 10 video solutions for The Skyline Problem, a hard level problem involving Array, Divide and Conquer, Binary Indexed Tree. This walkthrough by Tushar Roy - Coding Made Simple has 197,200 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |