Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

Given n buildings on a two-dimensional plane, find the skyline of these buildings.

Each building on the two-dimensional plane has a start and end x-coordinates, and a y-coordinate height. Skyline is defined as a unique representation of rectangular strips of different heights which are created after the overlap of multiple buildings on a two-dimensional plane.

The following picture demonstrates some buildings on the left side and their skyline on the right.

**Example**

Input:

5

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

From the image referenced above, we see the blue building at the start and the corresponding red dot in the right image at (2,10). The next change in skyline occurs at an x coordinate of 3 with the red building coming up at the height of 15, so in the output, the next line is printed as 3 15. Similarly, all the buildings are traversed to find the output as given in the sample output section.

**Notes**

Input Parameters: The input of buildings is given in a two-dimensional integer array format. The outer array contains multiple buildings where each building is an array of integers of size 3. The first integer represents the start coordinate of the building, the second integer represents the end coordinate of the building and the third integer represents its height.

Output: Return a two-dimensional integer array. The outer array has different rectangular strips, each element is an array of size two. The first element in the inner array is the x coordinate of the strip and the second element is the y coordinate of the strip (red dots in the image above).

Constraints:

- 1 <=
*n*<= 10^5 - 1 <=
*x, y, height*<= 2 * 10^9

** **A *BuildingIndex *class is defined in the solution consisting of three members:

*index:*it is the value of x-coordinate of the potential skyline point.*startEnd:*it is a character that denotes if this particular index is a start point or an end point of the building.*height:*it is the height of the building.

A priority queue named *priorityQ *is created. All the start and end points of all the buildings as objects of *BuildingIndex* class are added in this queue with the following insertion constraints:

- A lower value of
*index*gets priority. - If the
*index*values are the same,*'start'*point gets priority. - If two buildings are starting at the same
*index*, then*BuildingIndex*with higher*height*gets priority. - If two buildings are ending at the same
*index*, then*BuildingIndex*with smaller*height*gets priority.

A binary search tree named *heightCountQ *is created which stores the count of heights ordered by the heights of buildings.

Also, a variable named maxHeight is initialized with 0 which stores the current max height of the skyline.

Now pop elements from the *priorityQ*, one by one, till it is empty.

- If the popped element is the starting index, then check
- If it is greater than
*maxHeight*, if so add the start index and height pair to the*ans*list. - If the popped element is the end index, then check if it was the
*maxHeight*till now, if yes, then update the*ans*list with the current index and height from the next tallest building from the*heightCountQ.*And decrease the count in heightCountQ, if the count is 1, then the node is removed from the tree.

**Time Complexity:**

Sorting all the buildings as per the given constraints in the description would take O(2*n**log(2*n*)), where *n *is the number of buildings in the given array and 2**n* is the *BuildingIndex*. Also maintaining the count of heights take O(*n**log(*n*)), since each insertion and deletion is O(log(*n*)) in a BST.

So, the total time complexity is O(*n**log(*n*)).

**Auxiliary Space Used:**

The *priorityQ *and *heightCount* both require O(*n*) auxiliary space to store *n *buildings. So, total auxiliary space complexity is O(*n*).

**Space Complexity:**

Input and output arrays both require 3**n *and 2**n *amount of space respectively. Total space complexity including auxiliary space comes out to be O(*n*).

Note: Input and Output will already be taken care of.

Given n buildings on a two-dimensional plane, find the skyline of these buildings.

Each building on the two-dimensional plane has a start and end x-coordinates, and a y-coordinate height. Skyline is defined as a unique representation of rectangular strips of different heights which are created after the overlap of multiple buildings on a two-dimensional plane.

The following picture demonstrates some buildings on the left side and their skyline on the right.

**Example**

Input:

5

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

From the image referenced above, we see the blue building at the start and the corresponding red dot in the right image at (2,10). The next change in skyline occurs at an x coordinate of 3 with the red building coming up at the height of 15, so in the output, the next line is printed as 3 15. Similarly, all the buildings are traversed to find the output as given in the sample output section.

**Notes**

Input Parameters: The input of buildings is given in a two-dimensional integer array format. The outer array contains multiple buildings where each building is an array of integers of size 3. The first integer represents the start coordinate of the building, the second integer represents the end coordinate of the building and the third integer represents its height.

Output: Return a two-dimensional integer array. The outer array has different rectangular strips, each element is an array of size two. The first element in the inner array is the x coordinate of the strip and the second element is the y coordinate of the strip (red dots in the image above).

Constraints:

- 1 <=
*n*<= 10^5 - 1 <=
*x, y, height*<= 2 * 10^9

** **A *BuildingIndex *class is defined in the solution consisting of three members:

*index:*it is the value of x-coordinate of the potential skyline point.*startEnd:*it is a character that denotes if this particular index is a start point or an end point of the building.*height:*it is the height of the building.

A priority queue named *priorityQ *is created. All the start and end points of all the buildings as objects of *BuildingIndex* class are added in this queue with the following insertion constraints:

- A lower value of
*index*gets priority. - If the
*index*values are the same,*'start'*point gets priority. - If two buildings are starting at the same
*index*, then*BuildingIndex*with higher*height*gets priority. - If two buildings are ending at the same
*index*, then*BuildingIndex*with smaller*height*gets priority.

A binary search tree named *heightCountQ *is created which stores the count of heights ordered by the heights of buildings.

Also, a variable named maxHeight is initialized with 0 which stores the current max height of the skyline.

Now pop elements from the *priorityQ*, one by one, till it is empty.

- If the popped element is the starting index, then check
- If it is greater than
*maxHeight*, if so add the start index and height pair to the*ans*list. - If the popped element is the end index, then check if it was the
*maxHeight*till now, if yes, then update the*ans*list with the current index and height from the next tallest building from the*heightCountQ.*And decrease the count in heightCountQ, if the count is 1, then the node is removed from the tree.

**Time Complexity:**

Sorting all the buildings as per the given constraints in the description would take O(2*n**log(2*n*)), where *n *is the number of buildings in the given array and 2**n* is the *BuildingIndex*. Also maintaining the count of heights take O(*n**log(*n*)), since each insertion and deletion is O(log(*n*)) in a BST.

So, the total time complexity is O(*n**log(*n*)).

**Auxiliary Space Used:**

The *priorityQ *and *heightCount* both require O(*n*) auxiliary space to store *n *buildings. So, total auxiliary space complexity is O(*n*).

**Space Complexity:**

Input and output arrays both require 3**n *and 2**n *amount of space respectively. Total space complexity including auxiliary space comes out to be O(*n*).

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart