DSA problem
The Skyline Problem
A city's skyline is the outer contour of the silhouette formed by all the buildings when viewed from a distance. You are given the locations and heights of all the buildings as a 2D integer array buildings where buildings[i] = [left_i, right_i, height_i]. Each building is a rectangle in the xy-plane with its left and right edges at left_i and right_i respectively, and the top edge at height_i. Return the skyline as a list of "key points" [[x_1, y_1], [x_2, y_2], ...] sorted by x coordinate, where each key point is the left endpoint of some horizontal segment in the skyline except the last point with y = 0 marking the right end of the rightmost building.
The naive O(n * m) approach scans every x position against every building, which is computationally infeasible. The line-sweep formulation translates each rectangle into two events: a "start" event at x = left with height h, and an "end" event at x = right with height h. As we sweep left to right, we maintain the multiset of currently active building heights. Whenever the maximum changes between consecutive events, the new maximum becomes the next key point.
The classic trick for sorting events is to use (x, -h) for starts and (x, 0, h) for ends so that when two events share an x coordinate, starts come before ends (because -h < 0), and among ties of the same kind, taller starts come before shorter starts (because -h is more negative). This sorting ensures the skyline only emits a key point when the maximum height actually changes.
To efficiently track the running maximum, use a balanced multiset (Java TreeMap, C++ std::multiset) or a lazy heap pattern. Each event triggers an add or remove of one height. After processing each event, compare the current maximum to the previous skyline height; if it changed, emit [x, current_max]. The overall complexity is O(n log n) time and O(n) space.
Examples
buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]][[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]buildings = [[0,2,3],[2,5,3]][[0,3],[5,0]]buildings = [[1,2,1]][[1,1],[2,0]]Constraints
- 1 <= buildings.length <= 10^4
- 0 <= left_i < right_i <= 2^31 - 1
- 1 <= height_i <= 2^31 - 1
- buildings is sorted by left_i in non-decreasing order.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.