Scale Engineer

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
Line Sweep
Algorithms
Divide and Conquer
Data structures
ArrayHeap (Priority Queue)Binary Indexed TreeSegment TreeOrdered Set
Companies
Goldman SachsGoogleSiemensYelp

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]:

  • 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 <= 104
  • 0 <= lefti < righti <= 231 - 1
  • 1 <= heighti <= 231 - 1
  • buildings is sorted by lefti in 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

  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

Walkthrough

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:

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

Solutions

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

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.

← Previous

Previous problem

Next →

Next problem