# The Skyline Problem
**Difficulty:** HARD
[External](https://leetcode.com/problems/the-skyline-problem)
Canonical: https://scaleengineer.com/dsa/problems/the-skyline-problem
**Patterns:** [Line Sweep](https://scaleengineer.com/dsa/patterns/line-sweep)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Array, Heap (Priority Queue), Binary Indexed Tree, Segment Tree, Ordered Set
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Siemens](https://scaleengineer.com/companies/siemens), [Yelp](https://scaleengineer.com/companies/yelp), [Salesforce](https://scaleengineer.com/companies/salesforce), [Citadel](https://scaleengineer.com/companies/citadel), [X](https://scaleengineer.com/companies/x)
---
## Problem
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:**

![](https://assets.glich.co/dsa/the-skyline-problem/image0.jpg) 

**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 <= 104`
* `0 <= lefti < righti <= 231 - 1`
* `1 <= heighti <= 231 - 1`
* `buildings` is sorted by `lefti` in non-decreasing order.

# Approaches
## Brute Force Approach
The brute force approach involves checking the height at each x-coordinate by scanning through all buildings.
**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
**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
### Explanation
For each x-coordinate from the leftmost building to the rightmost building:
1. Find the maximum height among all buildings that contain this x-coordinate
2. If this height is different from the previous height, add it to the result

Here's the implementation:
```java
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;
    }
}
```
### Algorithm
1. Find the minimum and maximum x-coordinates among all buildings
2. 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
3. Add final point with height 0

## Divide and Conquer Approach
This approach splits the buildings array into two halves, solves each half recursively, and then merges the results.
**Time:** O(n log n) where n is number of buildings · **Space:** O(n) for recursive calls and temporary storage
**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
### Explanation
The approach works by:
1. Dividing buildings array into two halves
2. Recursively finding skyline for each half
3. Merging the two skylines similar to merge sort

Here's the implementation:
```java
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;
    }
}
```
### Algorithm
1. If only one building, return its skyline
2. Otherwise:
   - Split buildings into two halves
   - Recursively get skyline of each half
   - Merge the two skylines while maintaining height properties

## Priority Queue (Sweep Line) Approach
This approach uses a priority queue to keep track of building heights while sweeping through all critical points from left to right.
**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
**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
### Explanation
The approach works by:
1. Creating critical points from building edges
2. Sorting points by x-coordinate
3. Using max heap to track heights

Here's the implementation:
```java
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;
    }
}
```
### Algorithm
1. Create list of critical points (start and end of buildings)
2. Sort points by x-coordinate
3. 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

# Solutions
### Java

```java
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 ; } } }
```

### Python

```python
''' >>> 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)
```

### CPP

```cpp
// 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 ; } };
```