Description
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] = [lefti, righti, heighti]:
leftiis the x coordinate of the left edge of theithbuilding.rightiis the x coordinate of the right edge of theithbuilding.heightiis the height of theithbuilding.
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 [[x1,y1],[x2,y2],...]. 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.
Examples:
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]]Solution in Python
To solve the skyline problem in Python, we can use a sweep line algorithm combined with a max-heap. The basic idea is to process all critical points where the skyline could potentially change and then determine the contour formed by the buildings.
Python
import heapq
from typing import List
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
# List to store the result (skyline key points)
result = []
# List to store all the critical points (start and end of buildings)
events = []
# For each building, add the start and end events
for left, right, height in buildings:
# Start of a building has a negative height to indicate the building is starting
events.append((left, -height, right))
# End of a building has a positive height to indicate the building is ending
events.append((right, 0, 0))
# Sort events:
# 1. By x-coordinate
# 2. By height (starting events before ending events if they have the same x-coordinate)
events.sort()
# Max-heap to keep track of the current buildings' heights
# Initialize with a dummy building of height 0 ending at infinity
heap = [(0, float('inf'))]
# Current height to compare with the previous height
prev_height = 0
# Sweep through the sorted events
for x, neg_height, end in events:
# If it's the start of a building, add its height to the heap
if neg_height < 0:
heapq.heappush(heap, (neg_height, end))
# If it's the end of a building, remove it from the heap
else:
# Remove the building from the heap by filtering out the ended building
heap = [(h, r) for h, r in heap if r != x]
heapq.heapify(heap)
# Get the current max height from the heap
current_height = -heap[0][0]
# If the current max height changes from the previous height, it's a key point
if current_height != prev_height:
result.append([x, current_height])
prev_height = current_height
return resultExplanation:
- Events List:
- We create a list of events. Each building contributes two events:
- One when it starts (left edge, negative height).
- One when it ends (right edge, height zero).
- We create a list of events. Each building contributes two events:
- Sorting Events:
- We sort the events based on the x-coordinate. If two events have the same x-coordinate, the event with a lower height is processed first to correctly handle overlapping buildings.
- Max-Heap (Priority Queue):
- A max-heap (simulated using negative heights since Python’s
heapqis a min-heap by default) keeps track of the heights of the buildings that are currently active (i.e., buildings whose left edge has been encountered but the right edge has not yet been processed).
- A max-heap (simulated using negative heights since Python’s
- Processing Events:
- For each event:
- If it’s the start of a building, we push its height into the heap.
- If it’s the end of a building, we remove the building’s height from the heap.
- After each event, we check the maximum height in the heap. If this height has changed compared to the previous maximum height, this indicates a key point in the skyline, and we add it to the result.
- For each event:
- Result:
- The result list accumulates all key points that define the skyline.
Time Complexity:
- The time complexity is O(n log n) where nnn is the number of buildings. This is due to the sorting of events and the operations on the heap.
Space Complexity:
- The space complexity is O(n) for storing the events and the heap.
This approach efficiently computes the skyline by processing the critical points where changes in the skyline occur and managing the active buildings using a max-heap.
Solution in Javascript
JavaScript
/**
* @param {number[][]} buildings
* @return {number[][]}
*/
var getSkyline = function(buildings) {
// Result array to store the final key points of the skyline
const result = [];
// Array to store the critical points (start and end of each building)
const points = [];
// For each building, store the start and end points with corresponding heights
for (let [left, right, height] of buildings) {
points.push([left, -height]); // Use negative height to indicate start of a building
points.push([right, height]); // Use positive height to indicate end of a building
}
// Sort the points array
// 1. First by the x-coordinate.
// 2. If two points have the same x-coordinate, then by height.
// - Start of a building (-height) should come before end of a building (height)
points.sort((a, b) => {
if (a[0] !== b[0]) {
return a[0] - b[0];
}
return a[1] - b[1];
});
// Max Heap to keep track of the current building heights
const heights = [0];
// Current height of the skyline (initially 0)
let prevHeight = 0;
// Iterate over all points
for (let [x, h] of points) {
if (h < 0) {
// If it's a start of a building (height is negative), add the height to the heap
heights.push(-h);
} else {
// If it's an end of a building, remove the height from the heap
const index = heights.indexOf(h);
if (index > -1) {
heights.splice(index, 1);
}
}
// Get the current maximum height in the heap
const currentHeight = Math.max(...heights);
// If the current maximum height is different from the previous height,
// this is a critical point in the skyline.
if (currentHeight !== prevHeight) {
result.push([x, currentHeight]);
prevHeight = currentHeight;
}
}
return result;
};Solution in Java
Java
import java.util.*;
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
// List to store the result, which contains the key points of the skyline
List<List<Integer>> result = new ArrayList<>();
// List to store all critical points (start and end of each building)
List<int[]> points = new ArrayList<>();
// For each building, store its start and end points with respective heights
for (int[] building : buildings) {
int left = building[0];
int right = building[1];
int height = building[2];
// Start of a building, store with negative height
points.add(new int[]{left, -height});
// End of a building, store with positive height
points.add(new int[]{right, height});
}
// Sort the points
// 1. By x-coordinate
// 2. If x-coordinates are the same, then by height
points.sort((a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0]; // Sort by x-coordinate
}
return a[1] - b[1]; // Sort by height, with negative height first
});
// Max-heap (PriorityQueue) to keep track of current heights
PriorityQueue<Integer> heights = new PriorityQueue<>(Collections.reverseOrder());
// Initially, add height 0 to the heap
heights.add(0);
// Current height of the skyline (initially 0)
int prevHeight = 0;
// Iterate through all points
for (int[] point : points) {
int x = point[0];
int height = point[1];
if (height < 0) {
// Start of a building, add its height to the heap
heights.add(-height);
} else {
// End of a building, remove its height from the heap
heights.remove(height);
}
// Get the current maximum height in the heap
int currentHeight = heights.peek();
// If the current height is different from the previous height,
// this is a critical point in the skyline
if (currentHeight != prevHeight) {
// Add the current point to the result
result.add(Arrays.asList(x, currentHeight));
// Update the previous height
prevHeight = currentHeight;
}
}
return result;
}
}Solution in C#
C#
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public IList<IList<int>> GetSkyline(int[][] buildings) {
// List to store the result, which contains the key points of the skyline
List<IList<int>> result = new List<IList<int>>();
// List to store all critical points (start and end of each building)
List<int[]> points = new List<int[]>();
// For each building, store its start and end points with respective heights
foreach (var building in buildings) {
int left = building[0];
int right = building[1];
int height = building[2];
// Start of a building, store with negative height
points.Add(new int[] { left, -height });
// End of a building, store with positive height
points.Add(new int[] { right, height });
}
// Sort the points
// 1. By x-coordinate
// 2. If x-coordinates are the same, then by height
points.Sort((a, b) => {
if (a[0] != b[0]) {
return a[0] - b[0]; // Sort by x-coordinate
}
return a[1] - b[1]; // Sort by height, with negative height first
});
// Max-heap (SortedDictionary) to keep track of current heights
SortedDictionary<int, int> heightMap = new SortedDictionary<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
// Initially, add height 0 to the map
heightMap[0] = 1;
// Current height of the skyline (initially 0)
int prevHeight = 0;
// Iterate through all points
foreach (var point in points) {
int x = point[0];
int height = point[1];
if (height < 0) {
// Start of a building, add its height to the map
if (heightMap.ContainsKey(-height)) {
heightMap[-height]++;
} else {
heightMap[-height] = 1;
}
} else {
// End of a building, decrement or remove its height from the map
if (heightMap[height] > 1) {
heightMap[height]--;
} else {
heightMap.Remove(height);
}
}
// Get the current maximum height in the map
int currentHeight = heightMap.First().Key;
// If the current height is different from the previous height,
// this is a critical point in the skyline
if (currentHeight != prevHeight) {
// Add the current point to the result
result.Add(new List<int> { x, currentHeight });
// Update the previous height
prevHeight = currentHeight;
}
}
return result;
}
}