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.#218 The Skyline Problem asks you to compute the outer contour formed by overlapping buildings when viewed from a distance. A common strategy is the line sweep algorithm. Treat each building’s start and end as events on the x-axis and process them in sorted order. As the sweep line moves, maintain the current active building heights using a max heap (priority queue) so you can quickly determine the tallest building at any point. Whenever the maximum height changes, a new skyline key point is produced.
Another conceptual approach uses divide and conquer, where the skyline is recursively computed for halves of the building list and then merged similar to the merge step in merge sort. Both strategies rely on efficiently tracking height changes along the sweep. With appropriate data structures such as heaps or ordered sets, the algorithm typically runs in O(n log n) time with O(n) auxiliary space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Line Sweep with Max Heap | O(n log n) | O(n) |
| Divide and Conquer Skyline Merge | O(n log n) | O(n) |
Tushar Roy - Coding Made Simple
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.
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.
1import java.util.*;
2
3public class Skyline {
4 public List<List<Integer>> getSkyline(int[]
This Java implementation is similar to the Python approach. It collects all start and end events, processes them using a priority queue to keep track of the tallest buildings, and adds only the necessary key points to the result when there is a change in the skyline height.
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.
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.
1function
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, The Skyline Problem is a well-known hard interview question that appears in advanced algorithm rounds. It tests knowledge of line sweep techniques, heaps, and careful event processing.
A max heap (priority queue) is widely used to maintain the current active building heights during the sweep. Some implementations also use ordered sets, segment trees, or binary indexed trees to manage height updates efficiently.
The most common optimal approach is the line sweep algorithm combined with a max heap. By processing building start and end events along the x-axis and tracking the tallest active building, we can efficiently detect skyline changes in O(n log n) time.
The line sweep technique helps process building boundaries from left to right while dynamically tracking active heights. This makes it easy to detect when the tallest visible building changes and a new skyline point must be added.
The JavaScript solution applies a divide and conquer algorithm to split the problem space into manageable segments, solving for each individually, and consolidating results with aligned key height changes.