The Skyline Problem
Hard#0206Time: O(n * w) where n is number of buildings and w is width (max_x - min_x)Space: O(1) excluding the space needed for output7 companies
Patterns
Algorithms
Companies
Prompt
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]:
leftiis the x coordinate of the left edge of theithbuilding.rightiis the x coordinate of the right edge of theithbuilding.heightiis the height of theithbuilding.
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 - 1buildingsis sorted byleftiin non-decreasing order.
Approaches
3 approaches with complexity analysis and trade-offs.
The brute force approach involves checking the height at each x-coordinate by scanning through all buildings.
Algorithm
- Find the minimum and maximum x-coordinates among all buildings
- For each x-coordinate from min to max:
- Find maximum height among all buildings at current x
- If height changes from previous, add to result
- Add final point with height 0
Walkthrough
For each x-coordinate from the leftmost building to the rightmost building:
- Find the maximum height among all buildings that contain this x-coordinate
- If this height is different from the previous height, add it to the result
Here's the implementation:
class Solution { public List<List<Integer>> getSkyline(int[][] buildings) { // Find min and max x-coordinates int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE; for (int[] building : buildings) { minX = Math.min(minX, building[0]); maxX = Math.max(maxX, building[1]); } List<List<Integer>> result = new ArrayList<>(); int prevHeight = 0; // Check each x-coordinate for (int x = minX; x <= maxX; x++) { int maxHeight = 0; // Find max height at current x for (int[] building : buildings) { if (x >= building[0] && x < building[1]) { maxHeight = Math.max(maxHeight, building[2]); } } // If height changes, add to result if (maxHeight != prevHeight) { result.add(Arrays.asList(x, maxHeight)); prevHeight = maxHeight; } } // Add final point result.add(Arrays.asList(maxX, 0)); return result; }}Complexity
Time
O(n * w) where n is number of buildings and w is width (max_x - min_x)
Space
O(1) excluding the space needed for output
Trade-offs
Pros
Simple to understand and implement
Works for small inputs
No extra space needed except for output
Cons
Very inefficient for large inputs
Checks every x-coordinate even when unnecessary
Time complexity depends on width of skyline
This approach splits the buildings array into two halves, solves each half recursively, and then merges the results.
Algorithm
- If only one building, return its skyline
- Otherwise:
- Split buildings into two halves
- Recursively get skyline of each half
- Merge the two skylines while maintaining height properties
Walkthrough
The approach works by:
- Dividing buildings array into two halves
- Recursively finding skyline for each half
- Merging the two skylines similar to merge sort
Here's the implementation:
class Solution { public List<List<Integer>> getSkyline(int[][] buildings) { if (buildings.length == 0) return new ArrayList<>(); return getSkylineHelper(buildings, 0, buildings.length - 1); } private List<List<Integer>> getSkylineHelper(int[][] buildings, int left, int right) { if (left == right) { List<List<Integer>> result = new ArrayList<>(); result.add(Arrays.asList(buildings[left][0], buildings[left][2])); result.add(Arrays.asList(buildings[left][1], 0)); return result; } int mid = left + (right - left) / 2; List<List<Integer>> leftSkyline = getSkylineHelper(buildings, left, mid); List<List<Integer>> rightSkyline = getSkylineHelper(buildings, mid + 1, right); return mergeSkylines(leftSkyline, rightSkyline); } private List<List<Integer>> mergeSkylines(List<List<Integer>> left, List<List<Integer>> right) { List<List<Integer>> result = new ArrayList<>(); int h1 = 0, h2 = 0; int i = 0, j = 0; while (i < left.size() && j < right.size()) { int x, h; if (left.get(i).get(0) < right.get(j).get(0)) { x = left.get(i).get(0); h1 = left.get(i).get(1); i++; } else if (left.get(i).get(0) > right.get(j).get(0)) { x = right.get(j).get(0); h2 = right.get(j).get(1); j++; } else { x = left.get(i).get(0); h1 = left.get(i).get(1); h2 = right.get(j).get(1); i++; j++; } h = Math.max(h1, h2); if (result.isEmpty() || result.get(result.size() - 1).get(1) != h) { result.add(Arrays.asList(x, h)); } } while (i < left.size()) result.add(left.get(i++)); while (j < right.size()) result.add(right.get(j++)); return result; }}Complexity
Time
O(n log n) where n is number of buildings
Space
O(n) for recursive calls and temporary storage
Trade-offs
Pros
More efficient than brute force
Handles large inputs better
Divide and conquer strategy makes it easier to parallelize
Cons
More complex implementation
Requires additional space for recursion
Merging step can be tricky to implement correctly
This approach uses a priority queue to keep track of building heights while sweeping through all critical points from left to right.
Algorithm
- Create list of critical points (start and end of buildings)
- Sort points by x-coordinate
- Process points from left to right:
- For start point: add height to max heap
- For end point: remove height from max heap
- If max height changes, add point to result
Walkthrough
The approach works by:
- Creating critical points from building edges
- Sorting points by x-coordinate
- Using max heap to track heights
Here's the implementation:
class Solution { public List<List<Integer>> getSkyline(int[][] buildings) { // Prepare critical points List<int[]> points = new ArrayList<>(); for (int[] building : buildings) { points.add(new int[]{building[0], -building[2]}); // negative height for start point points.add(new int[]{building[1], building[2]}); // positive height for end point } // Sort by x-coordinate, if same then by height Collections.sort(points, (a, b) -> { if (a[0] != b[0]) return a[0] - b[0]; return a[1] - b[1]; }); // Use max heap to track heights PriorityQueue<Integer> heights = new PriorityQueue<>((a, b) -> b - a); heights.offer(0); // Add ground level List<List<Integer>> result = new ArrayList<>(); int prevHeight = 0; for (int[] point : points) { if (point[1] < 0) { // Start of building heights.offer(-point[1]); } else { // End of building heights.remove(point[1]); } int currentHeight = heights.peek(); if (currentHeight != prevHeight) { result.add(Arrays.asList(point[0], currentHeight)); prevHeight = currentHeight; } } return result; }}Complexity
Time
O(n log n) where n is number of buildings, due to sorting and heap operations
Space
O(n) for storing critical points and heap
Trade-offs
Pros
Most efficient approach
Handles all cases elegantly
Only processes critical points instead of all x-coordinates
Cons
Requires understanding of sweep line technique
Need to handle edge cases carefully
Memory usage is higher than brute force
Solutions
Solution
import java.util.* ; public class The_Skyline_Problem { public static void main ( String [] args ) { The_Skyline_Problem out = new The_Skyline_Problem (); Solution_Heap s = out . new Solution_Heap (); // output: [ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ] s . getSkyline ( new int [][]{ { 2 , 9 , 10 }, { 3 , 7 , 15 }, { 5 , 12 , 12 }, { 15 , 20 , 10 }, { 19 , 24 , 8 } } ) . stream (). forEach ( System . out :: println ); } class Solution_Heap { public List < List < Integer >> getSkyline ( int [][] buildings ) { List < List < Integer >> result = new ArrayList <>(); if ( buildings == null || buildings . length == 0 || buildings [ 0 ]. length == 0 ) { return result ; } List < Edge > edges = new ArrayList < Edge >(); // add all left/right edges for ( int [] each: buildings ) { edges . add ( new Edge ( each [ 0 ], each [ 2 ], true )); edges . add ( new Edge ( each [ 1 ], each [ 2 ], false )); } // sort edges, NlogN Collections . sort ( edges , ( a , b ) -> { if ( a . x != b . x ) { return Integer . compare ( a . x , b . x ); } if ( a . isStart && b . isStart ) { return Integer . compare ( b . height , a . height ); // higher edge at front } if (! a . isStart && ! b . isStart ) { return Integer . compare ( a . height , b . height ); // lower edge at front } return a . isStart ? - 1 : 1 ; // lower edge at front }); // process edges, comparator is reverseOrder() PriorityQueue < Integer > heightHeap = new PriorityQueue < Integer >( Collections . reverseOrder ()); for ( Edge edge : edges ) { if ( edge . isStart ) { if ( heightHeap . isEmpty () || edge . height > heightHeap . peek ()) { result . add ( Arrays . asList ( edge . x , edge . height )); } heightHeap . add ( edge . height ); } else { heightHeap . remove ( edge . height ); if ( heightHeap . isEmpty ()){ result . add ( Arrays . asList ( edge . x , 0 ) ); // last point } else if ( edge . height > heightHeap . peek ()){ // @note: intersect result . add ( Arrays . asList ( edge . x , heightHeap . peek ()) ); } } } return result ; } class Edge { int x ; // x坐标 int height ; boolean isStart ; public Edge ( int x , int height , boolean isStart ) { this . x = x ; this . height = height ; this . isStart = isStart ; } } } // merge sort example public class Solution_mergeSort { public List < int []> getSkyline ( int [][] buildings ) { if ( buildings == null || buildings . length == 0 ) { return new LinkedList < int []>(); } return getSkyline ( buildings , 0 , buildings . length - 1 ); } // NlogN private LinkedList < int []> getSkyline ( int [][] buildings , int lo , int hi ) { if ( lo < hi ) { int mid = lo + ( hi - lo ) / 2 ; return mergeSkylines ( getSkyline ( buildings , lo , mid ), getSkyline ( buildings , mid + 1 , hi )); } else { // lo == hi, base case, add the final already-merged building to skyline LinkedList < int []> skyline = new LinkedList < int []>(); skyline . add ( new int []{ buildings [ lo ][ 0 ], buildings [ lo ][ 2 ]}); // only care about [left-index, height] skyline . add ( new int []{ buildings [ lo ][ 1 ], 0 }); // right-index is just for last right edge return skyline ; } } // merge two Skylines private LinkedList < int []> mergeSkylines ( LinkedList < int []> skyline1 , LinkedList < int []> skyline2 ) { LinkedList < int []> skyline = new LinkedList < int []>(); int height1 = 0 , height2 = 0 ; while ( skyline1 . size () > 0 && skyline2 . size () > 0 ) { int index = 0 , height = 0 ; // @note: always remove the smaller index first, so order is guaranteed if ( skyline1 . getFirst ()[ 0 ] < skyline2 . getFirst ()[ 0 ]) { index = skyline1 . getFirst ()[ 0 ]; height1 = skyline1 . getFirst ()[ 1 ]; height = Math . max ( height1 , height2 ); skyline1 . removeFirst (); } else if ( skyline1 . getFirst ()[ 0 ] > skyline2 . getFirst ()[ 0 ]) { index = skyline2 . getFirst ()[ 0 ]; height2 = skyline2 . getFirst ()[ 1 ]; height = Math . max ( height1 , height2 ); skyline2 . removeFirst (); } else { index = skyline1 . getFirst ()[ 0 ]; height1 = skyline1 . getFirst ()[ 1 ]; height2 = skyline2 . getFirst ()[ 1 ]; height = Math . max ( height1 , height2 ); skyline1 . removeFirst (); skyline2 . removeFirst (); } if ( skyline . size () == 0 || height != skyline . getLast ()[ 1 ]) { skyline . add ( new int []{ index , height }); } } // final check skyline . addAll ( skyline1 ); skyline . addAll ( skyline2 ); return skyline ; } } }''' >>> a = [] >>> a.append((3, 5)) >>> a.append((3, -5)) >>> a.append((2, -10)) >>> a.append((2, 10)) >>> a [(3, 5), (3, -5), (2, -10), (2, 10)] >>> a.sort() >>> a [(2, -10), (2, 10), (3, -5), (3, 5)] >>> from queue import PriorityQueue >>> pq = PriorityQueue() >>> >>> pq.put([1,2,3]) >>> pq.put([-10,20,30]) >>> pq.put([11,22,33]) >>> >>> pq <Queue.PriorityQueue instance at 0x10aec51b8> >>> pq.queue[0][0] -10 >>> pq.get() [-10, 20, 30] >>> pq.queue[0][0] 1 ''' from queue import PriorityQueue class Solution : def getSkyline ( self , buildings : List [ List [ int ]]) -> List [ List [ int ]]: ans , lines , pq = [], [], PriorityQueue () for build in buildings : lines . extend ([ build [ 0 ], build [ 1 ]]) lines . sort () curbuilding , n = 0 , len ( buildings ) for line in lines : # 对于每一个边界线 lines[i]，找出所有包含 lines[i] 的建筑物 while curbuilding < n and buildings [ curbuilding ][ 0 ] <= line : pq . put ([ - buildings [ curbuilding ][ 2 ], buildings [ curbuilding ][ 0 ], buildings [ curbuilding ][ 1 ]]) # 建筑物的高度构建优先队列（大根堆），这里会包括line自己的building curbuilding += 1 while not pq . empty () and pq . queue [ 0 ][ 2 ] <= line : # higher at heap top after negated pq . get () # i.e. pop(), remove no-overlapping building high = 0 # 建筑物的左边界小于等于 lines[i]，右边界大于 lines[i]，则这些建筑物中高度最高的建筑物的高度就是该线轮廓点的高度 if not pq . empty (): high = - pq . queue [ 0 ][ 0 ] if len ( ans ) > 0 and ans [ - 1 ][ 1 ] == high : # 绿色建筑的左边的line，就要跳过 continue ans . append ([ line , high ]) return ans ############ ''' The solution uses a list called points to store the critical points and heights of the buildings. Each point is represented as a tuple (x, h), where x is the x-coordinate and h is the height. The points are sorted in ascending order based on the x-coordinate. The solution also uses a heap to store the heights in descending order. The heap is initialized with a height of 0. For each point, if the height is negative, it means it is the start of a building, so the negative height is added to the heap. If the height is positive, it means it is the end of a building, so the corresponding negative height is removed from the heap. After processing each point, the maximum height is obtained from the heap, and if it is different from the previous maximum height, the current point is added to the skyline. Finally, the skyline is returned, excluding the initial point (0, 0) that was added as a starting point. Note: The solution assumes that the input buildings is a list of tuples (left, right, height), where left and right represent the x-coordinates of the building's left and right edges, and height represents the height of the building. ''' import heapq class Solution : def getSkyline ( self , buildings ): # Create a list to store the critical points and heights points = [] for left , right , height in buildings : points . append (( left , - height )) # Start of building, negative height points . append (( right , height )) # End of building, positive height # Sort the points in ascending order based on x-coordinate # If two points have the same x-coordinate, the one with larger height comes first points . sort () # Create a heap to store the heights in descending order heights = [ 0 ] # Initialize the heap with a height of 0 skyline = [( 0 , 0 )] # Initialize the skyline with a point (0, 0) for x , h in points : if h < 0 : heapq . heappush ( heights , h ) # Add the negative height to the heap else : heights . remove ( - h ) # Remove the corresponding negative height from the heap heapq . heapify ( heights ) # Reorganize the heap # The current maximum height is the first element in the heap max_height = - heights [ 0 ] # If the maximum height has changed, add the current point to the skyline if max_height != skyline [ - 1 ][ 1 ]: skyline . append (( x , max_height )) return skyline [ 1 :] # Exclude the initial point (0, 0)// OJ: https://leetcode.com/problems/the-skyline-problem/ // Time: O(NlogN) // Space: O(N) // Ref: https://discuss.leetcode.com/topic/14939/my-c-code-using-one-priority-queue-812-ms bool cmp ( vector < int > & a , vector < int > & b ) { return a [ 0 ] < b [ 0 ]; } class Solution { public: vector < pair < int , int >> getSkyline ( vector < vector < int >>& buildings ) { vector < pair < int , int >> ans ; sort ( buildings . begin (), buildings . end (), cmp ); int i = 0 , x = 0 , y = 0 , N = buildings . size (); priority_queue < pair < int , int >> live ; // first: height, second: right while ( i < N || ! live . empty ()) { if ( i < N && ( live . empty () || live . top (). second >= buildings [ i ][ 0 ])) { x = buildings [ i ][ 0 ]; while ( i < N && buildings [ i ][ 0 ] == x ) { live . push ( make_pair ( buildings [ i ][ 2 ], buildings [ i ][ 1 ])); ++ i ; } } else { x = live . top (). second ; while ( ! live . empty () && live . top (). second <= x ) live . pop (); } y = live . empty () ? 0 : live . top (). first ; if ( ans . empty () || ans . back (). second != y ) ans . push_back ( make_pair ( x , y )); } return ans ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.