The Skyline Problem

Hard

Asked by:

+6

29 views

Topics:

ArraysStacksDynamic ProgrammingGreedy Algorithms

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array buildings where buildings[i] = [left_i, right_i, height_i]:

left_i is the x coordinate of the left edge of the i^th building.
right_i is the x coordinate of the right edge of the i^th building.
height_i is the height of the i^th 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 [[x₁,y₁],[x₂,y₂],...]. 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],...]

Example 1:

Input: buildings = [[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]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

Example 2:

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]

Constraints:

1 <= buildings.length <= 10⁴
0 <= left_i < right_i <= 2³¹ - 1
1 <= height_i <= 2³¹ - 1
buildings is sorted by left_i in non-decreasing order.

The Skyline Problem

Hard

Asked by:

29 views

Topics:

ArraysStacksDynamic ProgrammingGreedy Algorithms

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array buildings where buildings[i] = [left_i, right_i, height_i]:

left_i is the x coordinate of the left edge of the i^th building.
right_i is the x coordinate of the right edge of the i^th building.
height_i is the height of the i^th 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 [[x₁,y₁],[x₂,y₂],...]. 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],...]

Example 1:

Input: buildings = [[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]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

Example 2:

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]

Constraints:

1 <= buildings.length <= 10⁴
0 <= left_i < right_i <= 2³¹ - 1
1 <= height_i <= 2³¹ - 1
buildings is sorted by left_i in non-decreasing order.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the building dimensions (left, right, height)?
Can the input list of buildings be empty? If so, what should the output be?
If multiple buildings start or end at the same x-coordinate, how should I prioritize their heights in the skyline?
Is the input list of buildings guaranteed to be sorted by the left x-coordinate?
What should the output be if two key points have the same x-coordinate but different heights? Should I combine them into a single key point?

Brute Force Solution

Approach

The Skyline Problem asks us to draw the outline of a city given the shapes of its buildings. A brute-force approach imagines dividing the city's area into tiny vertical slices and checks each slice to see which buildings are present.

Here's how the algorithm would work step-by-step:

Imagine dividing the entire area where buildings are located into very small, equal-width vertical strips.
For each strip, check which buildings are covering that strip.
Find the tallest building covering each strip. That height represents the skyline's height at that point.
Repeat this process for every single strip across the entire area.
Connect the tops of these heights from strip to strip. Where heights change, these will form the corners of the skyline.
Finally, remove any unnecessary vertical lines to clean up the skyline drawing (for example, if the height of two adjacent strips is the same).

Code Implementation

def the_skyline_problem_brute_force(buildings):    if not buildings:        return []    minimum_left = min(building[0] for building in buildings)    maximum_right = max(building[1] for building in buildings)        # Divide the area into strips    skyline = []    for strip_position in range(minimum_left, maximum_right + 1):        max_height_for_strip = 0        # Find the tallest building in the current strip        for left_position, right_position, building_height in buildings:            if left_position <= strip_position < right_position:                max_height_for_strip = max(max_height_for_strip, building_height)                        if not skyline or skyline[-1][1] != max_height_for_strip:            skyline.append([strip_position, max_height_for_strip])                # Remove unnecessary vertical lines    final_skyline = []    for i in range(len(skyline)):        if i == 0 or skyline[i][1] != skyline[i-1][1]:            final_skyline.append(skyline[i])    return final_skyline

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – Let n be the number of buildings. The brute force approach iterates through a large number of vertical strips (discretized area) across the entire range of building locations. For each of these strips, it checks against every building to determine the tallest one covering that strip. This means for each strip, we iterate through all n buildings. If the number of strips is proportional to n (related to the number and distribution of buildings), then the algorithm performs approximately n (strips) * n (buildings) operations. Therefore, the overall time complexity is O(n²).

Space Complexity

O(N) – The brute-force approach, as described, iterates through a number of vertical strips covering the buildings' area. The number of these strips depends on the granularity chosen, but in the worst-case scenario, it can be proportional to N, where N is a factor representing the horizontal range covered by the buildings multiplied by the desired precision of the strips. For each strip, we are finding the tallest building, implying we need to store the height of the skyline at each strip, which leads to an auxiliary array or list of size proportional to N. Storing these heights requires O(N) space.

Optimal Solution

Approach

The efficient strategy involves processing building information in an ordered manner and keeping track of the highest buildings at each point. We simulate a 'sweep line' moving across the cityscape, updating the skyline as it encounters the start and end of buildings.

Here's how the algorithm would work step-by-step:

First, transform the building data into a series of 'events'. Each building generates two events: one for its start (left edge) and one for its end (right edge).
Sort these events based on their position on the ground (x-coordinate). If two events happen at the same position, prioritize the start of a building over the end.
As you 'sweep' across the events from left to right, maintain a record of the current heights of buildings using a special data structure that keeps the highest height easily accessible.
When you encounter the start of a building, add its height to the record.
When you encounter the end of a building, remove its height from the record.
Every time the maximum height in the record changes, it means the skyline's height has changed at that location. Record these changes as the coordinates of the skyline.
The final result is a list of coordinates representing the skyline's outline.

Code Implementation

import heapq

def get_skyline(buildings):
    skyline = []
    events = []

    # Convert buildings to events (start and end)
    for left, right, height in buildings:
        events.append((left, -height, right)) # Start event: height is negative
        events.append((right, 0, 0))         # End event: height is 0

    # Sort events by x coordinate, then by height (start events first)
    events.sort()

    live_buildings = [] # Priority queue to store current building heights
    current_max_height = 0

    for event_x, event_height, event_right in events:
        # Start of building
        if event_height < 0:
            heapq.heappush(live_buildings, (event_height, event_right))

        # End of building
        else:
            # Filtering out buildings that have already ended.
            while live_buildings and live_buildings[0][1] <= event_x:
                heapq.heappop(live_buildings)

        # Get current max height
        if live_buildings:
            new_max_height = -live_buildings[0][0]
        else:
            new_max_height = 0

        # If skyline height changes, add to result.
        if current_max_height != new_max_height:
            skyline.append([event_x, new_max_height])
            current_max_height = new_max_height

    return skyline

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The solution involves converting the building data into 2n events, where n is the number of buildings. Sorting these events based on their x-coordinate takes O(n log n) time. Iterating through these sorted events involves inserting and deleting heights into a data structure (like a priority queue or balanced tree) which maintains the maximum height. Each insertion and deletion operation on this data structure takes O(log n) time. Since we perform these operations for each of the 2n events, the total time complexity for these operations is O(n log n). Therefore, the overall time complexity is dominated by the sorting and height management, resulting in O(n log n).

Space Complexity

O(N) – The algorithm transforms the input buildings into a list of 2N events (start and end points). A data structure (like a heap or balanced tree) is used to keep track of the current building heights, which in the worst case can contain N elements (if all buildings overlap). The output skyline is also stored as a list of coordinates, which, in the worst case, can be of size O(N). Therefore, the auxiliary space is dominated by the event list and the data structure for tracking building heights, both of which are proportional to N.

Edge Cases

Case	How to Handle
Empty buildings array	Return an empty skyline list immediately as there are no buildings to process.
Buildings with the same start and end x-coordinates	Merge buildings with identical x coordinates by selecting the maximum height among them.
Buildings with zero height	Ignore these buildings as they do not contribute to the skyline.
Buildings with negative coordinates or heights	Handle negative coordinates by translating all buildings to positive space, or throw an error, and throw an error for negative heights as building heights cannot be negative.
Large number of buildings with small coordinate ranges	Ensure that the algorithm's space complexity is optimized to avoid excessive memory usage when processing numerous buildings within a confined area.
Integer overflow when calculating height differences or merging ranges	Use appropriate data types (e.g., long) to prevent integer overflow during calculations.
Overlapping buildings with same start and end x-coordinates, but different heights	Choose the largest height to represent the skyline at that x coordinate.
Very large x-coordinate values	Ensure that the data structures used to represent the skyline (e.g., arrays, trees) can accommodate these large values without performance degradation or memory issues.