The Skyline Problem
You are given 'N' rectangular buildings in a 2-dimensional city. Your task is to compute the skyline of these buildings, eliminating hidden lines return the skyline formed by these buildings collectively. A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. The geometric information of each building is given in the array of buildings where BUILDINGS[i] = [LEFT_i, RIGHT_i, HEIGHT_i]:

- LEFT_i is the x coordinate of the left edge of the ith building.

- RIGHT_i is the x coordinate of the right edge of the ith building.

- HEIGHT_i 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],...]. Also, the buildings are sorted by a non-decreasing order. For more clarification see sample case 1.

Input Format:

The first line of input contains a single integer ‘N’ denoting the number of buildings that would be given. And the rest of the ‘N’ lines contain three space-separated integers: Left and right Indices of the vertical edges of the building while the last integer represents the height of the building ‘H’.

Output Format :

Return the list of skylines formed by these buildings collectively. 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 on the left. The 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 is where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

The Skyline Problem

You are given 'N' rectangular buildings in a 2-dimensional city. Your task is to compute the skyline of these buildings, eliminating hidden lines return the skyline formed by these buildings collectively. A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. The geometric information of each building is given in the array of buildings where BUILDINGS[i] = [LEFT_i, RIGHT_i, HEIGHT_i]:

-> LEFT_i is the x coordinate of the left edge of the ith building.

-> RIGHT_i is the x coordinate of the right edge of the ith building.

-> HEIGHT_i 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],...]. 

Also, the buildings are sorted by a non-decreasing order.

For more clarification see sample case 1.

Input Format:

The first line of input contains a single integer ‘N’ denoting the number of buildings that would be given.

And the rest of the ‘N’ lines contain three space-separated integers: Left and right Indices of the vertical edges of the building while the last integer represents the height of the building ‘H’.

Output Format :

Return the list of skylines formed by these buildings collectively.

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 on the left.

The 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 is where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= | BUILDINGS | <= 10^4
0 <= LEFT_i < RIGHT_i <= 2^31 - 1
1 <= HEIGHT_i <= 2^31 - 1

Time Limit: 1 sec

Accepted Answer

Brute Force

The idea here is to first, sort the critical POINTS with respect to their coordinate and height pairs. Make a pair of 'X1' and take a negative of the height for the building so that 'X1' pairs are sorted before 'X2' pairs. Create a dictionary keeping the heights as keys and as soon as a left edge of a building is encountered, we add that building to the dictionary with its height as the key. When we encounter the right edge of a building, we remove that from the dictionary. When you hit the left edge of a building you add it to the dictionary, and when you hit the right edge of a building you delete the key. Finally, any time we encounter a critical point, after updating the dictionary we find the height of that critical point with maximum height value from keys that we already have in the dictionary to the value peeked from the top of the heap.

The algorithm will be-

Store the coordinates and heights of the buildings paired up with each other with the first building coordinate paired after taking negative of the height and the second coordinate with positive height in a list ‘POINTS’.
Now, sort edges present in the ‘POINTS’ list (array) in ascending order.
The positions are now sorted from left to right, small to large. Now, initialise a dictionary named 'HEIGHTS' with zero as its first key, having a value of 1 since this would be the last height that would be added.
Now, for each pair of an edge in the ‘POINTS’ list (array) and check:
1. Update the dictionary if the current edge is a start edge (with negative height) increment the value of the key by 1.
2. Delete the invalid buildings from the dictionary if an end edge is encountered for a key after decrementing its value by 1.
3. Now, In each iteration update the 'SKYLINE', which records the highest building from some position, and add it to the final list of our 'SKYLINE's if the current highest is no longer the tail of the 'SKYLINE' (previous highest).
We finally return the 'SKYLINE' list (array) that we have formed.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ denotes the number of buildings present in the given problem.

Since we are finding the skylines using a dictionary, therefore, we would require O(N) space for the problem.

Time Complexity: O(n^2)Explanation:

O(N * N), where ‘N’ denotes the number of buildings present in the given problem.

Since we are finding the skylines with a custom sort on the edges and heights, therefore along with finding the maximum among the keys (heights) available in the dictionary for each iteration, So, the time complexity will be O(N * N).

C++ (g++ 5.4)

/*
    Time Complexity: O(N^2)
    Space Complexity: O(N)

    where 'N' denotes the number of buildings present in the given problem.
*/

#include 

vector> getBuildingSkyline(vector>& buildings){
    
    vector> points;

    for(int i = 0; i < buildings.size(); i++){
        
        points.push_back({buildings[i][0], -buildings[i][2]});
        points.push_back({buildings[i][1], buildings[i][2]});   
    }

    sort(points.begin(), points.end());

    unordered_map heights;
    heights[0] = 1;

    int prevMax = 0;
    vector> res;

    for(int i = 0; i < points.size(); i++){
        int h = points[i].second;
        if(h < 0){
            heights[-h] += 1;
        }
        else{
            heights[h] -= 1;
            if(heights[h] == 0){
                heights.erase(h);
            }
        }

        int currMax = 0;        
        // The below line is O(n) which slows down the performance.
        for(auto j: heights){            
            currMax = max(currMax, j.first);            
        }

        if(currMax != prevMax){
            prevMax = currMax;
            int x = res.size();
            res.push_back(vector());
            res[x].push_back(points[i].first);
            res[x].push_back(currMax);
        }
    }

    return res;
}

Java (SE 1.8)

/*
    Time Complexity: O(N^2)
    Space Complexity: O(N)

    where 'N' denotes the number of buildings present in the given problem.
*/

import java.util.*;

public class Solution {
    public static int[][] getBuildingSkyline(int[][] buildings) {
        ArrayList points = new ArrayList();

        for(int i = 0; i < buildings.length; i++){     
            points.add(new int[]{buildings[i][0], -buildings[i][2]});
            points.add(new int[]{buildings[i][1], buildings[i][2]}); 
        }

        Collections.sort(points, new Comparator() {
            public int compare(int[] a, int[] b) {
                if(a[0] != b[0])
                {
                    return a[0] - b[0];
                }
                
                return a[1] - b[1];  
            }
        });

        Map heights = new HashMap();
        heights.put(0, 1);

        int prevMax = 0;
        ArrayList> res = new ArrayList>();

        for(int i = 0; i < points.size(); i++){
            int h = points.get(i)[1];
            if(h < 0){
                int c = (heights.containsKey(-h) ? heights.get(-h) : 0);
                heights.put(-h, c + 1);
            }
            else{
                int c = (heights.containsKey(h) ? heights.get(h) : 0);
                heights.put(h, c-1);
                if(heights.containsKey(h) && heights.get(h) == 0){
                    heights.remove(h);
                }
            }

            int currMax = 0;        
            // The below line is O(n) which slows down the performance.
            for(Map.Entry j : heights.entrySet()){            
                currMax = Math.max(currMax, j.getKey());            
            }

            if(currMax != prevMax){
                prevMax = currMax;
                int x = res.size();
                res.add(new ArrayList());
                res.get(x).add(points.get(i)[0]);
                res.get(x).add(currMax);
            }
        }
        
        int[][] ans = new int[res.size()][res.get(0).size()];
        for(int i = 0; i < res.size(); i++){
            for(int j = 0; j < res.get(i).size(); j++){
                ans[i][j] = res.get(i).get(j);
            }
        }

        return ans;
    }
}

Python (3.5)

'''

    Time Complexity: O(N^2)

    Space Complexity: O(N)



    where 'N' denotes the number of buildings present in the given problem.

'''



import collections





def getBuildingSkyline(buildings):



    points = []

    for x1, x2, h in buildings:

        points.append((x1, -h))

        points.append((x2, h))

    points.sort()



    heights = collections.defaultdict(int)

    heights[0] = 1

    prevMax = 0

    res = []



    for x, h in points:

        if h < 0:

            heights[-h] += 1

        else:

            heights[h] -= 1

            if heights[h] == 0:

                del heights[h]

                

        # The below line is O(n) which slows down the performance.

        currMax = max(heights.keys())

        if currMax != prevMax:

            prevMax = currMax

            res.append((x, currMax))

    return res

Accepted Answer

Sorting Based

The idea here is to first, sort the critical points. Then scan across the critical points from left to right. When we encounter the left edge of a rectangle, we add that rectangle to the heap with its height as the key. When we encounter the right edge of a rectangle, we remove that rectangle from the heap. As you scan, when you hit the left edge of a building you add it to the heap, and when you hit the right edge of a building you pop nodes off the top of the heap repeatedly until the top node is a building whose right edge is still ahead. With this strategy, your heap may contain buildings that have already ended, but it doesn’t matter because you’ll discard them as soon as they’re at the top of the heap. Finally, any time we encounter a critical point, after updating the heap we set the height of that critical point to the value peeked from the top of the heap.

The algorithm will be-

Sort edges with [POSITION, -HEIGHT, VALID_UNTIL]. Here, the first two elements are for iterating edges with the correct sequence, while, the last one is for popping out invalid buildings during the iteration.
The positions are now sorted from left to right, small to large.
When positions are overlapped, sort the height from high to low, large to a small image
Now, for each edge:
1. Pop-out invalid buildings from the top of the heap (there might still exist invalid ones in the heap, but we just want to make sure the top of the heap is valid).
2. And update the heap if the current edge is a start edge
3. In each iteration update the 'SKYLINE', which records the highest building from some position, if the current highest is no longer the tail of the 'SKYLINE' (previous highest).
We finally return the 'SKYLINE' list (array) that we have formed.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ denotes the number of buildings present in the given problem.

Since we are finding the skylines using a heap, therefore, we would require O(N) space for the problem.

Time Complexity: O(nlogn)Explanation:

O(N * log(N)), where ‘N’ denotes the number of buildings present in the given problem.

Since we are finding the skylines with a custom heap sort on the edges and heights, therefore, the time complexity will be O(N * log(N)).

Python (3.5)

'''

    Time Complexity: O(N * log(N))

    Space Complexity: O(N)



    where 'N' denotes the number of buildings present in the given problem.

'''



import sys

from heapq import heappush, heappop





def getBuildingSkyline(buildings):

    '''

        [start, -height, validUntil]

        height > 0: start edge

        height == 0: end edge

    '''

    edges = sorted([[l, -h, r] for l, r, h in buildings] +

                   [[r, 0, sys.maxsize] for l, r, h in buildings])



    prevHighest = [(0, sys.maxsize)]



    skyline = []

    for edge in edges:

        position, curHeight, validUntil = edge[0], -edge[1], edge[2]



        while prevHighest[0][1] <= position:

            # The equal term guarantees that, for end edges, popping from hight to low still works.

            heappop(prevHighest)



        if curHeight > 0:

            # Start edge.

            heappush(prevHighest, (-curHeight, validUntil))



        # 'prevHighest' is now the current highest.

        if not skyline or skyline[-1][1] != -prevHighest[0][0]:

            skyline.append([position, -prevHighest[0][0]])



    return skyline

Java (SE 1.8)

/*
    Time Complexity: O(N * log(N))
    Space Complexity: O(N)

    where 'N' denotes the number of buildings present in the given problem.
*/

import java.util.*;

public class Solution {
    public static int[][] getBuildingSkyline(int[][] buildings) {
        /*
            [start, -height, validUntil]
            height > 0: start edge
            height == 0: end edge
        */

        ArrayList edges = new ArrayList();
        for(int i = 0; i < buildings.length; i++){
            int x = edges.size();
            edges.add(new int[3]);
            edges.get(x)[0] = (buildings[i][0]);
            edges.get(x)[1] = (buildings[i][2]);
            edges.get(x)[2] = (buildings[i][1]);
        }

        for(int i = 0; i < buildings.length; i++){
            int x = edges.size();
            edges.add(new int[3]);
            edges.get(x)[0] = (buildings[i][1]);
            edges.get(x)[1] = (0);
            edges.get(x)[2] = (Integer.MAX_VALUE);
        }

        Collections.sort(edges, new Comparator() {
            public int compare(int[] a, int[] b) {
                    if(a[0] != b[0])
                    {
                        return a[0] - b[0];
                    }
                
                return b[1] - a[1];
            }   
        });

        PriorityQueue prevHighest = new PriorityQueue(2, (a, b) -> {
            if(a[0] != b[0])
            {
                return b[0] - a[0];
            }

            return a[1] - b[1];
        });

        prevHighest.add(new int[]{0, Integer.MAX_VALUE});

        ArrayList skyline = new ArrayList();

        for(int i = 0; i < edges.size(); i++){
            
            int position = edges.get(i)[0];
            int curHeight = edges.get(i)[1];
            int validUntil = edges.get(i)[2];

            while(prevHighest.peek()[1] <= position){
                /*
                    The equal term guarantees that, for end edges, popping 
                    from height to low still works.
                */
                prevHighest.poll();
            }
            
            if(curHeight > 0){
                // Start edge.
                prevHighest.add(new int[]{curHeight, validUntil});
            }
            
            // prevHighest is now the current highest.

            if(skyline.size() == 0){
                skyline.add(new int[2]);
                skyline.get(0)[0] = (position);
                skyline.get(0)[1] = (prevHighest.peek()[0]);  
            }
            else if(skyline.get(skyline.size()-1)[1] != prevHighest.peek()[0]){
                int x = skyline.size();
                skyline.add(new int[2]);
                skyline.get(x)[0] = (position);
                skyline.get(x)[1] = (prevHighest.peek()[0]);   
            }
        }

        int[][] ans = new int[skyline.size()][2];
        for(int i = 0; i < skyline.size(); i++){
            for(int j = 0; j < 2; j++){
                ans[i][j] = skyline.get(i)[j];
            }
        }  

        return ans;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity: O(N * log(N))
    Space Complexity: O(N)

    where 'N' denotes the number of buildings present in the given problem.
*/

#include 

vector> getBuildingSkyline(vector>& buildings){
    
    /*
        [start, -height, validUntil]
        height > 0: start edge
        height == 0: end edge
    */

    vector> edges;
    for(int i = 0; i < buildings.size(); i++){
        int x = edges.size();
        edges.push_back(vector());
        edges[x].push_back(buildings[i][0]);
        edges[x].push_back(-buildings[i][2]);
        edges[x].push_back(buildings[i][1]);
    }

    for(int i = 0; i < buildings.size(); i++){
        int x = edges.size();
        edges.push_back(vector());
        edges[x].push_back(buildings[i][1]);
        edges[x].push_back(0);
        edges[x].push_back(1e9);
    }

    sort(edges.begin(), edges.end());

    priority_queue, vector>, greater>> prevHighest;

    prevHighest.push({0, 1e9});

    vector> skyline;

    for(int i = 0; i < edges.size(); i++){
        
        int position = edges[i][0];
        int curHeight = -1*edges[i][1];
        int validUntil = edges[i][2];

        while(prevHighest.top().second <= position){
            /*
                The equal term guarantees that, for end edges, popping 
                from height to low still works.
            */
            prevHighest.pop();
        }
        
        if(curHeight > 0){
            // Start edge.
            prevHighest.push({-curHeight, validUntil});
        }
        
        // prevHighest is now the current highest.

        if(skyline.size() == 0){
            skyline.push_back(vector());
            skyline[0].push_back(position);
            skyline[0].push_back(-prevHighest.top().first);
        }
        else if(skyline.back()[1] != -prevHighest.top().first){
            int x = skyline.size();
            skyline.push_back(vector());
            skyline[x].push_back(position);
            skyline[x].push_back(-prevHighest.top().first);   
        }
    }

    return skyline;
}

-> LEFT_i is the x coordinate of the left edge of the ith building.

-> RIGHT_i is the x coordinate of the right edge of the ith building.

-> HEIGHT_i is the height of the ith building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

Note:

Input Format:

Output Format :

Note:

Constraints:

Top Bajaj Finserv Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Bajaj Finserv Software Developer