218. The Skyline Problem

HardBinary Indexed TreeSegment TreeArrayDivide and ConquerOrdered SetLine SweepHeap (Priority Queue)
Leetcode Link

Problem Description

In this problem, we are given a set of buildings in a city and are asked to compute the city's skyline. A skyline is essentially the outer contour created by all the buildings when viewed from a distance. Each building is represented by three integers, the x-coordinate of its left edge (left), the x-coordinate of its right edge (right), and its height (height). The aim is to return a list of all 'key points' that outline this contour.

A 'key point' is an x-coordinate paired with a height (y-coordinate), where there is a change in the skyline's height. These points are collected into a list where each element has the form [x, y] and represents the start of a new horizontal line in the skyline. The last point in the list always ends with a height of 0, indicating the end of the skyline to the rightmost building's end.

The result must be sorted by the x-coordinate, and it cannot contain consecutive horizontal lines of the same height. Instead, such lines should be merged into a single line.

Intuition

The intuition behind the solution is to process all buildings and simulate the construction of the skyline by bracketing the start and end of each building's influence on the skyline. A priority queue is used to keep track of the tallest building that's currently affecting the skyline since that will determine the outer contour at any point.

  1. Collecting Edges: Gather all the possible "edge" positions from the buildings' start and end points. These are the candidates for where the skyline could possibly change.

  2. Sorting Edges: By sorting the edges, we are simulating the horizontal scanline moving from left to right across the city.

  3. Using a Priority Queue: As we pass each edge, we use a priority queue to add buildings when we cross their start point and remove them when we cross their end point. The priority queue always keeps the highest building at the top, so we can easily find out which building defines the sky at a given edge.

  4. Updating the Skyline: While going through the edges, we check if the current max height changes after adding or removing buildings from our priority queue. If there is a change in height, this represents a key point in our skyline, and we record it. We also make sure to skip any consecutive edges of the same height to satisfy the condition of no consecutive horizontal lines with equal height.

  5. Building the Output: The key points are added to the skys list, which becomes our final answer representing the entire skyline as per the problem's requirements.

By processing the edges in sorted order and updating the priority queue, we efficiently calculate the key points of the skyline without having to simulate every possible x-coordinate, which would be less efficient.

Learn more about Segment Tree, Divide and Conquer, Line Sweep and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

How does merge sort divide the problem into subproblems?

Solution Approach

The solution follows a step-by-step approach using data structures like Priority Queue and list manipulation. Here's a breakdown of the key stages of the implementation:

  1. Initializing Data Structures: A list skys is initialized to hold the resultant skyline's key points. A separate list lines is used to collect all potential x-coordinates (both left and right edges of all buildings). A Priority Queue pq is used to store buildings currently part of the skyline. Each building is stored as a tuple (-height, left, right) in the priority queue to keep the tallest buildings at the top (as Priority Queue in Python is a min-heap, we store the height as negative to simulate a max-heap).

  2. Sorting the Edges: The lines array is sorted to prepare for a left-to-right scan across all potential key points.

  3. Processing Buildings: A while-loop is used to process all x-coordinates one by one in lines. Nested loops are then used to manipulate the priority queue as follows:

    • A loop adds buildings to the queue that start at or before the current line (x-coordinate), effectively saying that they now contribute to the skyline.
    • Another loop removes buildings from the queue whose right edge is at or before the current line, meaning they no longer contribute to the skyline.

  4. Determining the Current Height: After buildings are added or removed, the height of the current skyline is determined by the top element's height in the priority queue. If the priority queue is empty, this height is 0.

  5. Updating the Skyline: Before adding a new key point to skys, the algorithm checks whether the current height is the same as the last recorded height to avoid consecutive horizontal lines of the same height. If the height is different, a new key point [line, height] is appended to skys.

  6. Edge Cases Handling: The uniqueness of key points is maintained by only adding a new key point when the height differs from the previous key point. This automatically handles edge cases and ensures no consecutive horizontal lines of equal height as prescribed by the problem statement.

In summary, by employing a scanning line algorithm that steps through the sorted x-coordinates and a max-heap implemented by a priority queue to keep track of the tallest building(s) influencing the skyline, this solution approach efficiently constructs the skyline by dynamically determining the key points where the contour changes.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the following set of buildings represented as [left, right, height] tuples:

1Buildings: [(1, 5, 11), (2, 7, 6), (3, 9, 13), (12, 16, 7), (14, 25, 3)]

  1. Initializing Data Structures: We initialize skys to an empty list, lines to store potential x-coordinates, and pq as an empty Priority Queue.

  2. Collecting Edges: We gather all edges from the buildings.

1lines = [1, 5, 2, 7, 3, 9, 12, 16, 14, 25]
  1. Sorting the Edges: We sort the edges.
1lines = [1, 2, 3, 5, 7, 9, 12, 14, 16, 25]

  1. Processing Buildings: We process each x-coordinate in lines.

    • We pass the x-coordinate 1 and add the building (1, 5, 11) to the priority queue.
    • Passing x-coordinate 2, we add the building (2, 7, 6) to the priority queue.
    • At x-coordinate 3, we add (3, 9, 13); the priority queue now has buildings with heights 11, 6, and 13 at the top.

  2. Determining the Current Height: After the addition of buildings at x-coordinate 3, the height of the current skyline is from the top element of the priority queue, which is 13 (the height of the building at the top of the priority queue).

  3. Updating the Skyline: Since 13 is the starting height of the skyline, our first key point is [1, 13]. As we pass through x-coordinates 5 and 7, buildings will be removed from the priority queue, possibly altering the height.

  4. Continuing the Process: As we reach x-coordinate 9, the skyline is at height 0 since building (3, 9, 13) was the last to contribute and has now ended.

  5. More Updates: As we move to x-coordinate 12, we add (12, 16, 7) to our priority queue, and since the height now changes from 0 to 7, a new key point [12, 7] is added to skys.

  6. Edge Cases Handling: If at any point the current height is the same as the last recorded height, we do not add it to skys to avoid consecutive lines of the same height. For example, when building (14, 25, 3) starts at x-coordinate 14, the height does not change as it is less than the current height 7. So no new key point is added.

  7. Completing the Skyline: The last key point will be [25, 0] as it indicates the end of the skyline with the height dropping back to 0 after building (14, 25, 3) ends.

The output for the skyline would be the skys list:

1skys = [[1, 13], [9, 0], [12, 7], [16, 0], [25, 0]]

This list represents the changing points of the silhouette of the buildings when viewed from afar, without any redundant points, and it defines the skyline of the city according to the problem's statement.

Solution Implementation

1from queue import PriorityQueue
2
3class Solution:
4    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
5        # Initialize the skyline results array, a list to store building edges,
6        # and a priority queue to manage the current highest buildings
7        skyline = []
8        edges = []
9        max_heights = PriorityQueue()
10      
11        # Create a sorted list of all critical points (building start and end)
12        for building in buildings:
13            edges.extend([building[0], building[1]])
14        edges.sort()
15      
16        # Initialize pointers and get the total number of buildings
17        building_index, total_buildings = 0, len(buildings)
18
19        # Process each edge in the sorted list to determine skyline changes
20        for edge in edges:
21            # Add buildings to the priority queue which start before or at the current edge
22            while building_index < total_buildings and buildings[building_index][0] <= edge:
23                # Insert into the priority queue the negative height (to reverse the default order),
24                # the start, and the end of the current building
25                max_heights.put([-buildings[building_index][2], buildings[building_index][1]])
26                building_index += 1
27          
28            # Remove buildings from priority queue which end before the current edge
29            while not max_heights.empty() and max_heights.queue[0][1] <= edge:
30                max_heights.get()
31
32            # The height is 0 if there are no buildings in sight, or the highest if there are
33            height = -max_heights.queue[0][0] if not max_heights.empty() else 0
34          
35            # Only add a point to the skyline if the height changes from the last point
36            if not skyline or skyline[-1][1] != height:
37                skyline.append([edge, height])
38      
39        return skyline
40
1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5import java.util.Set;
6import java.util.TreeSet;
7
8public class Solution {
9  
10    // Function to calculate the skyline of a set of buildings
11    public List<int[]> getSkyline(int[][] buildings) {
12        Set<Integer> positions = new TreeSet<>(); // TreeSet to hold unique, sorted positions (edges of buildings)
13        Map<Integer, Integer> positionIndexMap = new HashMap<>(); // Maps original positions to their index after compression
14
15        // Collect all potential start and end points from the buildings
16        for (int[] building : buildings) {
17            positions.add(building[0]);
18            positions.add(building[1]);
19        }
20
21        // Create a map from position to index (for easier access, reduction of positions)
22        int index = 0;
23        for (int pos : positions) {
24            positionIndexMap.put(pos, index++);
25        }
26
27        // Create an array to store the maximum height at each position
28        int[] heights = new int[positionIndexMap.size()];
29      
30        // Determine the maximum height for each compressed position
31        for (int[] building : buildings) {
32            int beginIndex = positionIndexMap.get(building[0]); // Compressed start index
33            int endIndex = positionIndexMap.get(building[1]); // Compressed end index
34          
35            // Set the maximum height within the range of the current building
36            for (int i = beginIndex; i < endIndex; ++i) {
37                heights[i] = Math.max(heights[i], building[2]);
38            }
39        }
40
41        List<int[]> result = new ArrayList<>(); // List to hold the skyline points
42      
43        // Iterator to track positions
44        Integer previousPosition = null;
45      
46        // Construct the result list with actual positions and the corresponding heights
47        for (int pos : positions) {
48            int mappedIndex = positionIndexMap.get(pos);
49            int currentHeight = heights[mappedIndex];
50
51            // Add point to skyline if it is the start or height changes
52            if (previousPosition == null || currentHeight != heights[positionIndexMap.get(previousPosition)]) {
53                result.add(new int[]{pos, currentHeight});
54                previousPosition = pos; // Update the previousPosition after adding to result
55            }
56        }
57
58        return result; // Return the result skyline
59    }
60}
61
1#include <vector>
2#include <set>
3#include <map>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9    // Function to calculate the skyline of a set of buildings
10    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
11        set<int> positions; // Set to hold unique positions (edges of buildings)
12        map<int, int> positionIndexMap; // Maps original positions to their index after compression
13
14        // Collect all potential start and end points from the buildings
15        for (const auto& building : buildings) {
16            positions.insert(building[0]);
17            positions.insert(building[1]);
18        }
19
20        // Create a map from position to index (for easier access, reductions of positions)
21        int index = 0;
22        for (int pos : positions)
23            positionIndexMap.insert({pos, index++});
24
25        // Create a vector to store the maximum height at each position
26        vector<int> heights(positionIndexMap.size(), 0);
27      
28        // Determine the maximum height for each compressed position
29        for (const auto& building : buildings) {
30            const int beginIndex = positionIndexMap[building[0]]; // Compressed start index
31            const int endIndex = positionIndexMap[building[1]]; // Compressed end index
32          
33            // Set the maximum height within the range of current building
34            for (int i = beginIndex; i < endIndex; ++i)
35                heights[i] = max(heights[i], building[2]);
36        }
37
38        vector<pair<int, int>> result; // Vector to hold the skyline points
39        vector<int> mappedPositions(positions.begin(), positions.end()); // Expanded positions from the set to a vector
40      
41        // Construct the result vector with actual positions and the corresponding heights
42        for (size_t i = 0; i < heights.size(); ++i) {
43            // Following line prevents undefined behavior by checking the boundary before accessing `heights[i+1]`
44            if (i + 1 >= heights.size() || heights[i] != heights[i + 1])
45                result.emplace_back(mappedPositions[i], heights[i]);
46        }
47
48        // Return the result skyline
49        return result;
50    }
51};
52
1// Global Set to hold unique positions (edges of buildings)
2const positions: Set<number> = new Set();
3
4// Maps original positions to their index after compression
5const positionIndexMap: Map<number, number> = new Map();
6
7/**
8 * Function to calculate the skyline of a set of buildings.
9 * @param buildings Array of buildings where each building is represented as [left, right, height].
10 * @returns The skyline as an array of tuples [x, height].
11 */
12function getSkyline(buildings: number[][]): [number, number][] {
13    // Collect all potential start and end points from the buildings
14    buildings.forEach(building => {
15        positions.add(building[0]);
16        positions.add(building[1]);
17    });
18
19    // Create a map from position to index (for easier access, reduce use of positions)
20    let index = 0;
21    positions.forEach(pos => {
22        positionIndexMap.set(pos, index++);
23    });
24
25    // Create an array to store the maximum height at each position
26    const heights: number[] = new Array(positionIndexMap.size).fill(0);
27
28    // Determine the maximum height for each compressed position
29    buildings.forEach(building => {
30        const beginIndex = positionIndexMap.get(building[0])!; // Compressed start index
31        const endIndex = positionIndexMap.get(building[1])!; // Compressed end index
32
33        // Set the maximum height within the range of the current building
34        for (let i = beginIndex; i < endIndex; ++i) {
35            heights[i] = Math.max(heights[i], building[2]);
36        }
37    });
38
39    // Array to hold the skyline points
40    const result: [number, number][] = [];
41
42    // Expanded positions from the set to an array
43    const mappedPositions: number[] = [...positions].sort((a, b) => a - b);
44
45    // Construct the result array with actual positions and the corresponding heights
46    for (let i = 0; i < heights.length; ++i) {
47        // Check the boundary before accessing `heights[i + 1]` to prevent undefined behavior
48        if (i + 1 >= heights.length || heights[i] != heights[i + 1]) {
49            result.push([mappedPositions[i], heights[i]]);
50        }
51    }
52
53    // Return the result skyline
54    return result;
55}
56
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Time and Space Complexity

Time Complexity

The time complexity of this code primarily comes from several operations: the sort operation on lines, the two while-loops that run within the for-loop iterating over lines, and the priority queue operations.

  1. Sorting lines: Sorting an array has a time complexity of O(n log n), where n is the number of elements to sort. In the worst case, each building contributes two lines, so if we have k buildings, we will have 2k lines, leading to O(2k log(2k)) which simplifies to O(k log k).

  2. First while-loop: This loop inserts buildings into the priority queue. Insertion into a priority queue (min-heap or max-heap) is O(log m), where m is the number of elements in the priority queue. In the worst case scenario, all k buildings might be inserted, leading to O(k log k).

  3. Second while-loop: This loop removes buildings from the priority queue. The worst-case removal from a priority queue is also O(log m). However, this operation will be bounded by the number of buildings k, not the number of lines. So in the worst case, all k buildings might be removed, leading to a worst-case time complexity of O(k log k).

  4. Priority queue operations: The call to pq.empty() is O(1), and accessing the top element using pq.queue[0] is also O(1). However, the pq.put() and pq.get() operations inside the while-loops have O(log k) complexity per operation, contributing to the overall complexity when considering the loop iterations.

Given that these operations are not nested but rather sequential, the total worst-case time complexity is the sum of the individual complexities: O(k log k + k log k + k log k), which simplifies to O(k log k).

Space Complexity

The space complexity is dictated by the space needed to store the lines, skys, and the contents of the priority queue pq.

  1. Storing lines: We store at most 2k line starts and ends from k buildings, so the space needed for lines is O(k).

  2. Storing skys: In the worst case, each line could result in a change in height, meaning the skys array could have as many as 2k entries, which is O(k).

  3. Priority queue pq: The priority queue can hold at most k buildings at any given time, since that's the max number of buildings we have. So the space complexity is O(k) for the priority queue.

Adding these up, the space complexity of the algorithm is O(k + k + k) which simplifies to O(k).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following uses divide and conquer strategy?

Recommended Readings

Segment Tree

Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well

Divide and Conquer Intro

https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger

Line-Sweep Introduction

Line Sweep Introduction The primary motivation for this algorithm is for geometry related problems that we encounter in computer science Deeply rooted in geometric problem solving it has become an essential tool for tackling questions related to shapes lines or points on a Cartesian plane At its heart the line

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ