What is the Skyline Problem in Python?

Key takeaways:
The Skyline Problem involves drawing the outline of buildings on a 2D plane based on their positions and heights. The goal is to find the shape of the skyline when viewed from a distance.
The Skyline Problem has applications in computer graphics and urban planning.
It combines sorting, heap-based data structures, and event-driven computation, showcasing algorithm design and optimization.
This problem is commonly asked in technical interviews as it tests problem-solving skills, understanding of data structures, and algorithmic efficiency.

What is the Skyline Problem?

The Skyline Problem is a popular computer science interview question. It involves drawing an outline of several buildings in a 2D plane. This problem provides an excellent opportunity to explore and apply various programming concepts, such as sorting, divide and conquer, and data structures.

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 $\text{buildings}[i] = [\text{left}_i,~\text{right}_i,\text{height}_i]$ :

$\text{left}_i$ is the $x$ –coordinate where the $i^{th}$ building starts.
$\text{right}_i$ is the $x$ –coordinate where the $i^{th}$ building ends.
$\text{height}_i$ 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 $[\cdots,[1, 4], [3, 6], [5, 6], [7, 6], [8, 3], \cdots]$ is incorrect. The three lines with height $6$ should be combined into one, so the correct version would be $[\cdots, [1, 4], [3, 6], [8, 3], \cdots]$ .

Examples

Solution to find the skyline

The Skyline Problem aims to represent the outline of a set of rectangular buildings when viewed from a distance. This is achieved by identifying key points where the height of the silhouette changes. To solve this problem efficiently, an optimized sweepA sweep refers to the process of iterating over a line, typically from left to right, across a given dimension (e.g., the x-axis in the skyline problem), while systematically handling events or changes that occur along that line. line algorithm is used. The approach leverages a max heap to dynamically track the heights of active buildings, ensuring efficient height retrieval and pruningPruning refers to the process of removing invalid or inactive heights from the max heap. of inactive buildings.

Here are the detailed steps of the algorithm:

Start by creating a list of critical pointsCritical points are the x-coordinates where the height of the skyline changes. These points represent significant events where a building either starts or ends, influencing the overall skyline shape. for all buildings. For each building [left, right, height]:
1. Add a “start” event (left, -height) to indicate the start of the building.
2. Add an “end” event (right, height) to indicate the end of the building.
3. The negative height in “start” events ensures taller buildings are processed first when sorting, preventing incorrect skyline calculations. It also ensures “start” events are handled before “end” events at the same x-coordinate, maintaining correct height transitions.
Sort the critical points by x-coordinate. If two points have the same x-coordinate, prioritize “start” events (negative height) over “end” events (positive height) to handle overlaps correctly.
Next, initialize the following data structures:
1. A max_heap as an empty list to track active building heights.
2. A dictionary active_heights to store counts of building heights, ensuring efficient pruning.
  1. When a building’s endpoint is reached, its height remains in the max_heap until explicitly removed. To ensure the max_heap reflects only active buildings, we prune heights that no longer correspond to valid buildings.
3. A variable prev_max_height set to 0.
4. An empty list result to store the key points of the skyline.
Process each critical point (x, height) in the sorted list:
1. If height < 0 (start event), add the building height to active_heights and push its negative to max_heap.
2. Otherwise, decrement active_heights or remove the corresponding height in active_heights if active_heights = 0.
3. While max_heap is not empty, and the tallest building in max_heap is no longer active (not in active_heights), remove it from the max heap.
4. Compute the current maximum height as -max_heap[0] if the heap is not empty, or 0 if it is.
5. If the current maximum height differs from prev_max_height, record the change by appending [x, current_max_height] to result and update prev_max_height.
Return result as the list of key points defining the skyline.

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

from heapq import heappush, heappop
from collections import defaultdict
def get_skyline(buildings):
    # Create critical points
    critical_points = []
    for left, right, height in buildings:
        critical_points.append((left, -height))  # Start of a building
        critical_points.append((right, height))  # End of a building
    # Sort critical points
    critical_points.sort(key=lambda x: (x[0], x[1]))
    # Data structures
    max_heap = []
    active_heights = defaultdict(int)
    prev_max_height = 0
    result = []
    # Process each critical point
    for x, height in critical_points:
        if height < 0:  # Start of a building
            heappush(max_heap, height)
            active_heights[-height] += 1
        else:  # End of a building
            active_heights[height] -= 1
            if active_heights[height] == 0:
                del active_heights[height]
        # Clean up the heap
        while max_heap and -max_heap[0] not in active_heights:
            heappop(max_heap)
        # Determine the current max height
        current_max_height = -max_heap[0] if max_heap else 0
        # Check if the height has changed
        if current_max_height != prev_max_height:
            result.append([x, current_max_height])
            prev_max_height = current_max_height
    return result
def main():
    buildings = [
        [[1, 7, 9], [3, 8, 8], [5, 9, 7]],
        [[1, 5, 10]],
        [[1, 2, 3], [4, 5, 6], [7, 8, 9]],
        [[1, 2, 5], [2, 3, 8]],
        [[0, 2, 10], [1, 2, 10], [2, 3, 10]],
        [[1000, 2000, 50], [1500, 2500, 80], [3000, 4000, 60]]
    ]
    for i, building in enumerate(buildings, 1):
        print(f"{i}. \tBuildings =", building)
        print("\tSkyline =", get_skyline(building))
        print("-" * 100)
if __name__ == "__main__":
    main()

The Skyline Problem

Complexity analysis

Time complexity:

The overall time complexity of the solution is $O(n \log n)$ :

The algorithm sorts all critical points. Since there are $2$ events for each building (start and end), the total number of events is $2n$ , where $n$ is the number of buildings.
- Sorting takes $O(2n \log (2n))$ , which simplifies to $O(n \log n)$ .
Each event is processed once, and for each event:
- Adding or removing an element in the max-heap takes $O(\log n)$ time.
- Cleaning the heap involves checking the top of the heap and removing inactive elements, which can also take $O(\log n)$ time per operation in the worst case.
- The total number of operations related to the heap is proportional to the number of events, $2n$ . Thus, the heap operations contribute $O(2n \log n)$ , which simplifies to $O(n \log n)$ .

Space complexity:

The overall space complexity of the solution is $O(n)$ :

Storing $2n$ critical points requires $O(2n)$ , which simplifies to $O(n)$ .
The max-heap stores at most $n$ active buildings, requiring $O(n)$ space.
The dictionary stores counts of building heights, also requiring $O(n)$ space in the worst case.

Additional resources

To learn more about data structures and algorithms and practice more LeetCode-based problems such as The Skyline Problem, look at the following list of curated courses at Educative:

If you wish to implement your solution in C++, then take a look at the “The Skyline Problem” available on the Grokking Coding Interview Patterns in C++ course.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

Why are critical points sorted before processing?

Sorting ensures that events are processed in left-to-right order. If two events occur at the same x-coordinate, “start” events are processed before “end” events to handle overlaps correctly and prioritize taller buildings.

What are some real-world applications of the skyline problem?

Applications include urban planning, where city layouts are modeled visually and shadow mapping in computer graphics, etc.

How does the algorithm handle buildings with the same height?

Buildings with the same height are treated as independent. The max-heap ensures that all active buildings are considered, and overlapping buildings with the same height do not create redundant key points.

Can this problem be solved using Union-Find or other data structures?

Yes, alternative data structures such as Union-Find (Disjoint Set Union) or Segment Trees could be used to solve this problem.

Free Resources

What is the Skyline Problem in Python?