Solution: The Skyline Problem
Let’s solve The Skyline problem using the Union-find pattern.
We'll cover the following
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
left
i
is the-coordinate where the building starts. right
i
is the-coordinate where the building ends. height
i
is the height of thebuilding.
All buildings are rectangles that sit on flat ground (height
Note: The output skyline should not have multiple horizontal lines at the same height in a row. For example, an output like
is incorrect. The three lines with height should be combined into one, so the correct version would be .
Constraints:
buildings.length
left
i
right
i
height
i
buildings
is sorted byleft
i
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 sizen
with all values set to 0. This will store the maximum height at each x-coordinate.A dictionary
indexMap
that maps each x-coordinate to its index in the sortedcoordinates
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
indexMap
, convert the building’s left and right x-coordinates into indexes, whereleft
is the index of the left edge andright
is the index of the right edge.Run a
while
loop that continues as long asleft < right
:Call
find
to find the current root of theleft
index.If the found root
left
is still less thanright
:Call the
union
to merge theleft
with theright
. 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:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.