Solution: The Skyline Problem

Statement

Imagine standing at a distance, viewing the skyline of a city. The skyline is the shape formed by all the buildings in the city when viewed together. Your task is to determine the shape of this skyline, given all the buildings’ position and height. Each building is represented by three values in the array buildings, where $buildings[i] = [left_i,~right_i,~ height_i]$:

1. lefti is the $x$-coordinate where the $i^{th}$ building starts.

2. righti is the $x$-coordinate where the $i^{th}$ building ends.

3. heighti is the height of the $i^{th}$ building.

All buildings are rectangles that sit on flat ground (height $0$). The skyline should be a list of points that define its outline, with each point showing where the height changes as you move from left to right. The final point should have a height of $0$, marking where the last building ends.

Note: The output skyline should not have multiple horizontal lines at the same height in a row. For example, an output like $[...,[1, 4], [3, 6], [5, 6], [7, 6], [8, 3],...]$ is incorrect. The three lines with height $6$ should be combined into one, so the correct version would be $[...,[1, 4], [3, 6], [8, 3],...]$.

Constraints:

• $1 \leq$ buildings.length $\leq 10^3$

• $0 \leq$ lefti $<$ righti $\leq 10^4$

• $1 \leq$ heighti $\leq 10^4$

• buildings is sorted by lefti in ascending order.

Solution

This solution calculates a city’s skyline based on the outlines of buildings. Each building has a starting position, an ending position, and a height, and the solution combines these outlines to form the city’s skyline. The key challenge is merging adjacent buildings into a single outline, where the union-find pattern becomes useful. The intuition behind using union-find is that it allows us to merge overlapping segments of the skyline. Each building spans a range of x-coordinates; if two buildings overlap, their segments must be joined. Union-find helps manage which x-coordinates are connected to the same skyline component. By doing this, we can track the boundaries of the skyline and avoid redundant operations, such as recalculating the same segments multiple times.

Here’s the step-by-step implementation of the solution:

• First, sort and store all the buildings’ unique x-coordinates (left and right edges). Sorting the x-coordinates ensures that we build the skyline in the correct order from left to right.

• Next, initialize the following data structures:

  • A heights list of size n with all values set to 0. This will store the maximum height at each x-coordinate.

  • A dictionary index_map that maps each x-coordinate to its index in the sorted coordinates list. This allows for quick lookup of x-coordinate indexes later.

  • A union-find data structure to find and merge the overlapping building coordinates.

• Sort the buildings in descending order of height. This ensures that taller buildings are processed first because they define the shape of the skyline more prominently than shorter buildings.

• For each building (from tallest to shortest):

  • Using the index_map, convert the building’s left and right x-coordinates into indexes, where left is the index of the left edge and right is the index of the right edge.

  • Run a while loop that continues as long as left < right:

    • Call find to find the current root of the left index.

    • If the found root left is still less than right:

      • Call the union to merge the left with the right. This ensures that these two parts of the skyline are considered connected.

      • Update the heights[left] to the current building’s height.

      • Increment left by 1 to move to the next index.

• After processing all buildings, loop through the heights list to build the skyline:

  • To avoid redundant horizontal segments, only add a point to the skyline if its current height is different from the previous point’s height.

• Finally, return the skyline list, which contains the coordinates representing the city’s skyline. Each point marks where the height changes.

Let’s look at the following illustration to get a better understanding of the solution: