© Parineeth M R
Question 61. Find the skyline of a group of buildings
The skyline problem is pretty popular in coding interviews. Here we take an in depth look at how to solve the problem.
Consider the diagram below where there are 4 buildings: B1 (height = 20), B2 (height = 30), B3 (height = 40) and B4 (height = 10).
The resulting skyline of the buildings can be obtained by picking the height of the tallest building at each position. So for instance, at position = 1, the height of the tallest building is 20. At position = 2, the height of the tallest building is 40. The resulting skyline for the buildings is shown below
To solve the problem, let us first develop a notation for representing each building and a notation for representing the resulting skyline. Each building can be represented with its left position, right position and its height. So for instance in the diagram, building B1 can be represented as (left = 1, right = 4, height = 20).
Strip S1 is represented using point P1 (position = 1, height = 20).
Strip S2 is represented using point P2 (position = 2, height = 40).
Strip S3 is represented using point P3 (position = 6, height = 10).
When we indicate the point for the strip, it means that the strip starts at this point and the height of the strip continues till the next skyline point. So in the diagram above for strip S2 having point P2 (position = 2, height = 40), it means that the strip starts at position 2 and has a height of 40 till we reach the next point P3 at position 6
Note that the buildings given to us in the input need not be sorted based on the left position of the building. So for instance, the buildings can be input in the following order: B2, B4, B1, B3.
Brute force – In the brute force technique, we first start with a single building and compute the skyline of the first building. Then we go on adding one building at a time and re-compute the result skyline. This is similar to insertion sort. The result skyline will maintain the points in sorted order based on position. Each time we add a building, we have to find where we can insert it in the result skyline. This operation is O(n). Since we have to do this operation for n buildings, the time complexity is O(n2).
There is a more efficient solution that uses merge sort with time complexity O(nlogn). Given a group of unsorted buildings, we divide the group into two groups: G1 and G2. We then recursively find the skylines for the two groups and then merge the skylines of the two groups to get the result.
So in our example, as we recursively divide the group of buildings, we will finally reach the stage where we get individual buildings B1, B2, B3 and B4. Once we reach this stage, we can represent each building as a strip as shown in the diagram below
Each strip indicates the skyline for a single building. Now we need to recursively merge the skylines to get the final result. Each skyline formed during the merge can consist of one or more strips. The basic idea that we use to merge the skylines is to pick the maximum height of the two input skylines at all the positions. So we maintain two variables: H1 and H2. H1 is the current height of skyline of group 1 and H2 is the current height of skyline in group 2. H1 and H2 are initialized to 0
To merge the two skylines, traverse the two skylines, keep picking the left most point in the two skylines and perform the following
1. If the left most point lies in Group-1, then update the height H1 to the height of the left most point. The height of the result skyline at this point is H = max(H1, H2). Let the position of the left most point be P. Append a new point (P, H) to the result skyline. Then advance to the next point in Group-1.
2. If the left most point lies in Group-2, then update the height H2 to the height of the left most point. The height of the result skyline at this point is H = max(H1, H2). Let the position of the left most point be P. Append a new point (P, H) to the result skyline. Then advance to the next point in Group-2.
3. If the left most point in Group-1 is at the same position as the left most point in Group-2, then update H1 to the height of the left most point in Group-1 and H2 to the height of the left most point in Group-2. The height of the result skyline at this point is H = max(H1, H2). Let the position of the left most point be P. Append a new point (P, H) to the result skyline. Then advance to the next point in Group-1 and Group-2.
When appending a new point to the result skyline, we observe the following rules
– We will not maintain redundant strips in the result skyline. So if the height of new point being added to the result skyline is equal to the height of the last point in the result skyline, then there is no need to add the new point to the result skyline.
– There can’t be two points at the same position in the result skyline. So if the position of the new point being added to the result skyline is equal to the position of the last point in the result skyline, then pick maximum height of the new point and old point and store the maximum height at this position.
Consider the case where we are merging the skylines of building B1 and B2 to get the skyline R1.
At position P1, the height of building B1 is H1 = 20 and height of building B2 is H2 = 0. So max (H1, H2) = 20. So height of result skyline at P1 is 20.
At position P2, the height of B1 is H1 = 20 and height of B2 is H2 = 30. So max(H1, H2) = 30. So height of result skyline at P2 is 30.
At position P3, the height of B1 is H1 = 20 and height of B2 is H2 = 0. So max(H1, H2) = 20. So height of result skyline at P3 is 20.
At position P4, the height of B1 is H1 = 0 and height of B2 is H2 = 0. So max(H1, H2) = 0. So height of result skyline at P4 is 0.
The merging of the skylines B3 and B4 to get the skyline R2 is shown in the diagram below.
The merging of skyline R1 and R2 to get the final skyline result is shown below
The code for computing the skyline is given below
Python
#Main function for computing the skyline. This function is recursive.
#buildings: ArrayList containing information about the buildings. There should be
# at least one building. The input buildings need not be sorted
#low: smallest index of the group of building being processed
#high: largest index of the group of buildings being processed
def compute_skyline(buildings, low, high) :
if (low == high) :
#We have reached a single building. Create the result skyline
result = []
#Add the strip corresponding to left end of building to result
left = buildings[low].left
height = buildings[low].height
cur_strip = Strip(left, height)
result.append(cur_strip)
#Add the strip corresponding to right end of building to result.
#For the right end of the building, the height will be 0
left = buildings[low].right
height = 0
cur_strip = Strip(left, height)
result.append(cur_strip)
#Terminate the recursion and return the result skyline
return result
#Recursively compute skyline1 for (low, mid) and skyline2 for
#(mid+1, high) and then merge the two skylines
mid = (low + high) // 2
skyline1 = compute_skyline(buildings, low, mid)
skyline2 = compute_skyline(buildings, mid + 1, high)
result = merge(skyline1, skyline2)
return result
#Helper function that adds the current strip into the end of the skyline
def append(skyline, cur_strip) :
size = len(skyline)
#If the current strip to be added and the last strip of the skyline have
#the same left position, then pick the max height of the two strips and
#update the height of the last strip in the skyline and return
if (size > 0 and skyline[size - 1].left == cur_strip.left) :
skyline[size - 1].height = max(skyline[size - 1].height,
cur_strip.height)
return
#The current strip to be added has the same height as the last strip in
#skyline. So no need to add the current strip since neighboring strips
#in skyline should have unique heights. So simply return
if (size > 0 and skyline[size - 1].height == cur_strip.height) :
return
#The current strip to be added starts at a different position and has a
#different height than the last strip in the skyline. So add the current
#strip to the skyline
skyline.append(cur_strip)
#Helper function that merges skyline1 and skyline2 and returns the new merged
#skyline
def merge(skyline1, skyline2):
result = []
i = j = 0
#h1 keeps track of the current height in skyline1 and h2 keeps track of the
#current height in skyline2 as we traverse the two skylines
h1 = h2 = 0
while (i < len(skyline1) and j < len(skyline2)) :
#Pick the strip which is leftmost in the two skylines
if (skyline1[i].left < skyline2[j].left) :
h1 = skyline1[i].height #update current height of skyline1
#The height of the strip to be added to the result will have
#the maximum of the current heights of the two skylines
left = skyline1[i].left
height = max(h1, h2)
cur_strip = Strip(left, height)
append(result, cur_strip)
i += 1
elif (skyline1[i].left == skyline2[j].left):
h1 = skyline1[i].height #update current height of the skylines
h2 = skyline2[j].height
#The height of the strip to be added to the result will have
#the maximum of the current heights of the two skylines
left = skyline1[i].left
height = max(h1, h2)
cur_strip = Strip(left, height)
append(result, cur_strip)
i += 1
j += 1
else :
h2 = skyline2[j].height #update current height of skyline2
#The height of the strip to be added to the result will have
#the maximum of the current heights of the two skylines
left = skyline2[j].left
height = max(h1, h2)
cur_strip = Strip(left, height)
append(result, cur_strip)
j += 1
#Append the remaining strips in skyline1 to the result
while (i < len(skyline1)) :
append(result, skyline1[i])
i += 1
#Append the remaining strips in skyline2 to the result
while (j < len(skyline2)) :
append(result, skyline2[j])
j += 1
return result
C/C++
/*Main function for computing the skyline. This function is recursive.
buildings: vector containing information about the buildings. There should be
at least one building. The input buildings need not be sorted
low: smallest index of the group of building being processed
high: largest index of the group of buildings being processed*/
vector<strip> compute_skyline(vector<building_info>& buildings,
int low, int high)
{
if (low == high) {
/*We have reached a single building. Create the result skyline*/
vector<strip> result;
strip cur_strip;
/*Add the strip corresponding to left end of building to result*/
cur_strip.left = buildings[low].left,
cur_strip.height = buildings[low].height;
result.push_back(cur_strip);
/*Add the strip corresponding to right end of building to result.
For the right end of the building, the height will be 0*/
cur_strip.left = buildings[low].right;
cur_strip.height = 0;
result.push_back(cur_strip);
/*Terminate the recursion and return the result skyline*/
return result;
}
/*Recursively compute skyline1 for (low, mid) and skyline2 for
(mid+1, high) and then merge the two skylines*/
int mid = (low + high) / 2;
vector<strip> skyline1 = compute_skyline(buildings, low, mid);
vector<strip> skyline2 = compute_skyline(buildings, mid + 1, high);
vector<strip> result = merge(skyline1, skyline2);
return result;
}
/*Helper function that adds the current strip into the end of the skyline*/
void append(vector<strip>& skyline, strip& cur_strip)
{
int size = skyline.size();
/*If the current strip to be added and the last strip of the skyline have
the same left position, then pick the max height of the two strips and
update the height of the last strip in the skyline and return*/
if (size && skyline[size - 1].left == cur_strip.left) {
skyline[size - 1].height = max(skyline[size - 1].height,
cur_strip.height);
return;
}
/*The current strip to be added has the same height as the last strip in
skyline. So no need to add the current strip since neighboring strips
in skyline should have unique heights. So simply return*/
if (size && skyline[size - 1].height == cur_strip.height)
return;
/*The current strip to be added starts at a different position and has a
different height than the last strip in the skyline. So add the current
strip to the skyline*/
skyline.push_back(cur_strip);
}
/*Helper function that merges skyline1 and skyline2 and returns the new merged
skyline*/
vector<strip> merge(vector<strip>& skyline1,
vector<strip>& skyline2)
{
vector<strip> result;
int i = 0, j = 0;
/*h1 keeps track of the current height in skyline1 and h2 keeps track of the
current height in skyline2 as we traverse the two skylines*/
int h1 = 0, h2 = 0;
strip cur_strip;
while (i < skyline1.size() && j < skyline2.size()) {
/*Pick the strip which is leftmost in the two skylines*/
if (skyline1[i].left < skyline2[j].left) {
h1 = skyline1[i].height; /*update current height of skyline1*/
/*The height of the strip to be added to the result will have
the maximum of the current heights of the two skylines*/
cur_strip.left = skyline1[i].left;
cur_strip.height = max(h1, h2);
append(result, cur_strip);
++i;
} else if (skyline1[i].left == skyline2[j].left) {
h1 = skyline1[i].height; /*update current height of the skylines*/
h2 = skyline2[j].height;
/*The height of the strip to be added to the result will have
the maximum of the current heights of the two skylines*/
cur_strip.left = skyline1[i].left;
cur_strip.height = max(h1, h2);
append(result, cur_strip);
++i;
++j;
} else {
h2 = skyline2[j].height; /*update current height of skyline2*/
/*The height of the strip to be added to the result will have
the maximum of the current heights of the two skylines*/
cur_strip.left = skyline2[j].left;
cur_strip.height = max(h1, h2);
append(result, cur_strip);
++j;
}
}
/*Append the remaining strips in skyline1 to the result*/
while (i < skyline1.size()) {
append(result, skyline1[i]);
++i;
}
/*Append the remaining strips in skyline2 to the result*/
while (j < skyline2.size()) {
append(result, skyline2[j]);
++j;
}
return result;
}
Java
/*Main function for computing the skyline. This function is recursive.
buildings: ArrayList containing information about the buildings. There should be
at least one building. The input buildings need not be sorted
low: smallest index of the group of building being processed
high: largest index of the group of buildings being processed*/
public static ArrayList<Strip> computeSkyline(BuildingInfo [] buildings,
int low, int high) {
if (low == high) {
/*We have reached a single building. Create the result skyline*/
ArrayList<Strip> result = new ArrayList<Strip>();
/*Add the strip corresponding to left end of building to result*/
Strip curStrip = new Strip();
curStrip.left = buildings[low].left;
curStrip.height = buildings[low].height;
result.add(curStrip);
/*Add the strip corresponding to right end of building to result.
For the right end of the building, the height will be 0*/
curStrip = new Strip();
curStrip.left = buildings[low].right;
curStrip.height = 0;
result.add(curStrip);
/*Terminate the recursion and return the result skyline*/
return result;
}
/*Recursively compute skyline1 for (low, mid) and skyline2 for
(mid+1, high) and then merge the two skylines*/
int mid = (low + high) / 2;
ArrayList<Strip> skyline1 = computeSkyline(buildings, low, mid);
ArrayList<Strip> skyline2 = computeSkyline(buildings, mid + 1, high);
ArrayList<Strip> result = merge(skyline1, skyline2);
return result;
}
/*Helper function that adds the current strip into the end of the skyline*/
public static void append(ArrayList<Strip> skyline, Strip curStrip) {
int size = skyline.size();
/*If the current strip to be added and the last strip of the skyline have
the same left position, then pick the max height of the two strips and
update the height of the last strip in the skyline and return*/
if (size > 0 && skyline.get(size - 1).left == curStrip.left) {
skyline.get(size - 1).height = Math.max(skyline.get(size - 1).height,
curStrip.height);
return;
}
/*The current strip to be added has the same height as the last strip in
skyline. So no need to add the current strip since neighboring strips
in skyline should have unique heights. So simply return*/
if (size > 0 && skyline.get(size - 1).height == curStrip.height)
return;
/*The current strip to be added starts at a different position and has a
different height than the last strip in the skyline. So add the current
strip to the skyline*/
skyline.add(curStrip);
}
/*Helper function that merges skyline1 and skyline2 and returns the new merged
skyline*/
public static ArrayList <Strip> merge(ArrayList<Strip> skyline1,
ArrayList<Strip> skyline2) {
ArrayList <Strip> result = new ArrayList <Strip>();
int i = 0, j = 0;
/*h1 keeps track of the current height in skyline1 and h2 keeps track of the
current height in skyline2 as we traverse the two skylines*/
int h1 = 0, h2 = 0;
Strip curStrip;
while (i < skyline1.size() && j < skyline2.size()) {
/*Pick the strip which is leftmost in the two skylines*/
if (skyline1.get(i).left < skyline2.get(j).left) {
h1 = skyline1.get(i).height; /*update current height of skyline1*/
/*The height of the strip to be added to the result will have
the maximum of the current heights of the two skylines*/
curStrip = new Strip();
curStrip.left = skyline1.get(i).left;
curStrip.height = Math.max(h1, h2);
append(result, curStrip);
++i;
} else if (skyline1.get(i).left == skyline2.get(j).left) {
h1 = skyline1.get(i).height; /*update current height of the skylines*/
h2 = skyline2.get(j).height;
/*The height of the strip to be added to the result will have
the maximum of the current heights of the two skylines*/
curStrip = new Strip();
curStrip.left = skyline1.get(i).left;
curStrip.height = Math.max(h1, h2);
append(result, curStrip);
++i;
++j;
} else {
h2 = skyline2.get(j).height; /*update current height of skyline2*/
/*The height of the strip to be added to the result will have
the maximum of the current heights of the two skylines*/
curStrip = new Strip();
curStrip.left = skyline2.get(j).left;
curStrip.height = Math.max(h1, h2);
append(result, curStrip);
++j;
}
}
/*Append the remaining strips in skyline1 to the result*/
while (i < skyline1.size()) {
append(result, skyline1.get(i));
++i;
}
/*Append the remaining strips in skyline2 to the result*/
while (j < skyline2.size()) {
append(result, skyline2.get(j));
++j;
}
return result;
}