The Skyline Problem

HARD

Description

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] = [left_i, right_i, height_i]:

left_i is the x coordinate of the left edge of the i^th building.
right_i is the x coordinate of the right edge of the i^th building.
height_i is the height of the i^th 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 [[x₁,y₁],[x₂,y₂],...]. 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 <= 10⁴
0 <= left_i < right_i <= 2³¹ - 1
1 <= height_i <= 2³¹ - 1
buildings is sorted by left_i in non-decreasing order.

Approaches

Checkout 3 different approaches to solve The Skyline Problem. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

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

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 Analysis

Time Complexity: O(n * w) where n is number of buildings and w is width (max_x - min_x)Space Complexity: O(1) excluding the space needed for output

Pros and Cons

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

Code Solutions

Checking out 3 solutions in different languages for The Skyline Problem. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for The Skyline Problem

Algorithms:

Divide and Conquer

Patterns:

Line Sweep

Data Structures:

ArrayHeap (Priority Queue)Binary Indexed TreeSegment TreeOrdered Set

Companies:

Goldman Sachs |Google |Siemens |Yelp |