The Skyline 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.
  
Now suppose you are given the locations and heights of all the buildings, write a program to output the skyline formed by these buildings collectively. Location of building is specified using tuple [x1,x2,h] where 'x1' is starting point of a building, 'x2' is where building ends and 'h' is height of the building. The skyline would be returned as a set of key points.
Starting point of each horizontal line segment of the skyline is marked as a key point. Complete skyline therefore could be specified using set of such key points.

For example, if input is an array of building co-ordinates: [[2,9,10], [13,15,10]] then the output should be the skyline specified as [[2,10],[9,0],[13,10],[15,0]]. In the below diagram, input buildings are shown on the left hand side and the  output is shown on the right hand side with highlighted key points.


If input is  [[2,9,10], [3,6,15], [5,12,12], [13,16,10], [13,16,10], [15,17,5]]  then the output should be [[2,10], [3,15], [6,12], [12,0], [13,10], [16,5], [17,0]] as shown below.


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

A naive approach which runs in O(n^2) goes like this -
1. Mark key points for each given building separately by using key point definition(start of a horizontal line segment).'
2. Add all key points to the output skyline.
3. Now for each key point in the skyline, if buildings with more height overlap with it then change key point's 'y' co-ordinate to the height of the tallest overlapping building.
3. Finally, remove redundant key points from the output skyline.


An optimized algorithm takes merge-sort like approach which runs in O(n.log(n)) time.
Base case:
If there is only one building with specification as [x0,x1,h](starts at x0, ends at x1 and has height of 'h'), then there are only two key-point to be returned - [x0,h] and [x1,0]

Recursive step:
Divide the given set of buildings into two halves recursively and obtain skylines for these two halves.

And for merging these two skylines which are specified using set of key-points use the following procedure.

Initialize last seen height of both skylines to 0.
1. Compare key points of given two skylines starting from leftmost end. Choose the key point from the skyline which has lesser of 'x' values.
2. If 'y' value of chosen key point is less than last seen height of other skyline, update chosen key point's 'y' co-ordinate to last seen height of other skyline.
3. Add chosen key point to merged skyline.
4. The skyline from which the key point was picked in step #1, update the last seen height of that skyline to chosen key point's original 'y' co-ordinate(and not the updated 'y' in step #2).
5. Proceed to next key point of the chosen skyline to be compared with key point of other skyline.
6. In step #1, if key points from both the skylines have same 'x' value then chose the key-point which has greater 'y' co-ordinate, add that key point to merged skyline, advance key points for both the skylines and update last seen height for both skylines.
7. Repeat steps 1-7 till key points from both the skylines are not added into the merged skyline.
8. Remove redundant key points from the merged skyline.

If you are not able to completely understand this algorithm, please go through the code and watch the video above which illustrates this algorithm using animations.

Please add comments below in case you have any feedback/queries.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.nilesh.questions;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * The Skyline Problem.
 * @author Nilesh
 */
public class SkylineSolution 
{
    private int greater(int a, int b)
    {
        if (a > b) return a;
        return b;
    }
    
    // given two skylines, merge them
    private List<int[]> mergeSkylines(List<int[]> skylineListLower, List<int[]> skylineListHigher)
    {
        int h1 = 0, h2 = 0;
        int newIndex = 0;
        List<int[]> skylineMerged = new ArrayList<int[]>();;
    
        while (true)
        {
            if (skylineListLower.isEmpty() || skylineListHigher.isEmpty())
            {
                break;
            }
            
            // first key points from both the skylines
            int [] stripe1 = skylineListLower.get(0);
            int [] stripe2 = skylineListHigher.get(0);
            
            // 0: 'x' co-ordinate, 1: height
            int [] mergedStripe = new int[2];
            
            // comparing 'x' co-ordinates of current key points of skyline-1 and skyline-2 
            if (stripe1[0] < stripe2[0]) // key point from skyline-1 is chosen 
            {
                mergedStripe[0] = stripe1[0];
                mergedStripe[1] = stripe1[1];
            
                // if 'y' co-ordinate for key point from skyline-1 is less than last seen height of skyline-2
                // then we need to update merged key point's 'y' co-ordinate to last seen height of skyline-2
                if (stripe1[1] < h2)
                {
                    mergedStripe[1] = h2;
                }
                
                // update the last seen height for skyline-1
                // note that last seen height for skyline-2 is not updated 
                h1 = stripe1[1];
                
                // move to next key point for this skyline
                skylineListLower.remove(0);
            }
            else if (stripe2[0] < stripe1[0])
            {
                mergedStripe[0] = stripe2[0];
                mergedStripe[1] = stripe2[1];
                
                if (stripe2[1] < h1)
                {
                    mergedStripe[1] = h1;
                }
                
                // update the last seen height of skyline-2
                // note that last seen height of skyline-
                h2 = stripe2[1];
                
                skylineListHigher.remove(0);
            }
            
            // if 'x' co-ordinates of key points for both skylines are same
            // then choose the key point with greater 'y' value
            // advance key points for both and hence update last seen height for both
            else
            {
                mergedStripe[0] = stripe2[0];
                mergedStripe[1] = greater(stripe1[1], stripe2[1]);
                
                h1 = stripe1[1];
                h2 = stripe2[1];
                
                skylineListLower.remove(0);
                skylineListHigher.remove(0);
            }
            
            skylineMerged.add(mergedStripe);
        }
        
        if (skylineListLower.isEmpty())
        {
            while (!skylineListHigher.isEmpty())
            {
                skylineMerged.add(skylineListHigher.remove(0));
            }
        }
        else
        {
            while (!skylineListLower.isEmpty())
            {
                skylineMerged.add(skylineListLower.remove(0));
            }
        }
        
        // remove redundant key points from merged skyline 
        int current = 0;
        while (current < skylineMerged.size())
        {
            boolean dupeFound = true;
            int i = current + 1;
            while ((i < skylineMerged.size()) &&  dupeFound)
            {
                if (skylineMerged.get(current)[1] == skylineMerged.get(i)[1])
                {
                    dupeFound = true;
                    skylineMerged.remove(i);
                }
                else
                {
                    dupeFound = false;
                }
            }
            current += 1;
        }
        
        return skylineMerged;
    }

    private List<int[]> getSkyline(int low, int high, int[][]buildings)
    {
        List<int[]> skyLineList = new ArrayList<int[]>();

        // invalid case
        if (low > high)
        {
            return skyLineList;
        }
        // base case: if there is only one building, only two key points define the skyline for it
        else if (low == high)
        {
            int x1 = buildings[low][0];
            int x2 = buildings[low][1];
            int h  = buildings[low][2];
            
            int[] element1 = {x1, h}; // first key point
            int[] element2 = {x2, 0}; // second key point
            
            skyLineList.add(element1);
            skyLineList.add(element2);
            
            return skyLineList;
        }
        // general case
        else
        {
            int mid = (low + high) / 2;
            
            // get the skyline for lower half
            List<int[]> skylineListLower = getSkyline(low, mid, buildings);
         
            // get the skyline for upper half
            List<int[]> skylineListHigher = getSkyline(mid+1, high, buildings); 
            
            // merge skylines for these two halves
            return mergeSkylines(skylineListLower, skylineListHigher);  
        }
    }
    
    public List<int[]> getSkyline(int[][] buildings) 
    {
        return getSkyline(0, buildings.length-1, buildings);
    }
    
    public static void main(String[] args)
    {
        int[][] buildings = { {2,9,10}, {3,6,15}, {5,12,12}, {13,16,10}, {13,16,10}, {15,17,5}};
        
        SkylineSolution slnForSkyline = new SkylineSolution();
        
        List<int[]> skyLine = slnForSkyline.getSkyline(buildings);
        
        System.out.println("Skyline for given buildings would look like: ");
        for (int i = 0;  i < skyLine.size(); i++)
        {
            System.out.println(skyLine.get(i)[0]+","+skyLine.get(i)[1]);
        }
    }
}
		

Order of the Algorithm

Time Complexity is O(n.log(n))
Space Complexity is O(n)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.

    Nilesh More

    Ninja Programmer