The Skyline Problem solution and explanation
Google
9 more videos on this problem
Find the Skyline Problem with C++ Solution ExplainedmCoding · 10:49 · 55K views
The Skyline Problem || LeetcodePepcoding · 34:19 · 21K views
LeetCode 218. The Skyline ProblemHappy Coding · 19:02 · 13K views
Leetcode 218 | Skyline Problem (Array Sorting | PriorityQueue | Heap)The Tech Granth · 25:49 · 9K views
LeetCode 218. The Skyline Problem Explanation and Solutionhappygirlzt · 17:21 · 8K views
The SkyLineProblem | Leetcode 218| Leetcode November Challenge | Live coding sessionCoding Decoded · 13:34 · 7K views
Daily Leetcode #913: Sep 30, 2022 - 218. The Skyline ProblemProgramming Live with Larry · 21:01 · 2K views
Leetcode 218 The Skyline ProblemRen Zhang · 45:28 · 2K views
218. The Skyline Problem|| LeetCode || C++Code with Sky · 19:21 · 2K views
Skyline ProblemTushar Roy - Coding Made Simple · 22:54 · 204K views
The problem
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.
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 <= 1040 <= lefti < righti <= 231 - 11 <= heighti <= 231 - 1buildingsis sorted byleftiin non-decreasing order.
Approach overview
Problem Overview: You are given a list of buildings represented as [left, right, height]. Each building forms a rectangle on the skyline. The task is to compute the outer contour of all buildings combined and return the key points where the skyline height changes.
Approach 1: Sweep Line Algorithm with Priority Queue (O(n log n) time, O(n) space)
The most common solution treats building edges as events and processes them from left to right using a sweep line. Convert every building into two events: a start edge (height enters) and an end edge (height leaves). Sort all events by x-coordinate, then track active building heights with a max heap (priority queue). When the sweep line encounters a start edge, push the height into the heap; when it encounters an end edge, remove that height. The maximum value in the heap represents the current skyline height. Whenever this maximum changes, record a new key point. The heap ensures efficient retrieval of the tallest active building in O(log n). This approach is the standard solution for skyline and interval-overlay problems and heavily relies on techniques from Line Sweep and Heap (Priority Queue).
Approach 2: Divide and Conquer (O(n log n) time, O(n) space)
This method mirrors merge sort. Split the buildings array into two halves, recursively compute the skyline for each half, then merge the two skylines into a combined outline. During merging, iterate through both skyline lists while tracking the current heights from the left and right halves. The visible skyline at any x-coordinate is the maximum of the two heights. Whenever this maximum changes, append a new key point. The key challenge is merging two skyline outlines while eliminating redundant height segments. The recursive structure leads to O(n log n) time, similar to merge sort. This approach highlights algorithmic design patterns from Divide and Conquer and is useful when reasoning about skyline merging rather than event simulation.
Recommended for interviews: The sweep line with a priority queue is the approach most interviewers expect. It demonstrates understanding of event processing, heaps, and geometric interval problems. The divide and conquer solution is equally optimal but less commonly implemented under time pressure. Showing the sweep line idea first proves you recognize the canonical skyline technique.
Approach 1: Approach 1: Sweep Line Algorithm with Priority Queue
The Sweep Line algorithm involves moving a vertical line from left to right over the x-coordinates and maintaining a list of currently active buildings using a max-heap. The priority queue helps keep track of the tallest building at each point. As the line reaches the start of a new building, add it to the heap, and as it reaches the end of a building, remove it. The key points are detected based on changes in the maximum height at points where buildings start or end.
import heapq
def getSkyline(buildings):
events = [(L, -H, R) for L, R, H in buildings] + [(R, 0, 0) for _, R, _ in buildings]
events.sort()
res, hp = [[0, 0]], [(0, float('inf'))]
for L, negH, R in events:
while L >= hp[0][1]:
heapq.heappop(hp)
if negH:
heapq.heappush(hp, (negH, R))
if res[-1][1] != -hp[0][0]:
res.append([L, -hp[0][0]])
return res[1:]import java.util.*;
public class Skyline {
public List<List<Integer>> getSkyline(int[][] buildings) {
List<int[]> events = new ArrayList<>();
for (int[] b : buildings) {
events.add(new int[]{b[0], -b[2]});
events.add(new int[]{b[1], b[2]});
}
events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
List<List<Integer>> res = new ArrayList<>();
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
pq.add(0);
int prev = 0;
for (int[] e : events) {
if (e[1] < 0) {
pq.add(-e[1]);
} else {
pq.remove(e[1]);
}
int current = pq.peek();
if (prev != current) {
res.add(Arrays.asList(e[0], current));
prev = current;
}
}
return res;
}
}#include <vector>
#include <set>
#include <algorithm>
using namespace std;
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int>> events;
for (auto& b : buildings) {
events.emplace_back(b[0], -b[2]);
events.emplace_back(b[1], b[2]);
}
sort(events.begin(), events.end());
multiset<int> heights = {0};
vector<vector<int>> res;
int prev = 0;
for (const auto& e : events) {
if (e.second < 0) {
heights.insert(-e.second);
} else {
heights.erase(heights.find(e.second));
}
int current = *heights.rbegin();
if (current != prev) {
res.push_back({e.first, current});
prev = current;
}
}
return res;
}function getSkyline(buildings) {
const events = [];
for (const [left, right, height] of buildings) {
events.push([left, -height]);
events.push([right, height]);
}
events.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));
const result = [];
const heights = new Map();
heights.set(0, 1);
let prevMaxHeight = 0;
for (const [x, h] of events) {
if (h < 0) {
heights.set(-h, (heights.get(-h) || 0) + 1);
} else {
heights.set(h, heights.get(h) - 1);
if (heights.get(h) === 0) {
heights.delete(h);
}
}
const currentMaxHeight = Math.max(...heights.keys());
if (currentMaxHeight !== prevMaxHeight) {
result.push([x, currentMaxHeight]);
prevMaxHeight = currentMaxHeight;
}
}
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> GetSkyline(int[][] buildings) {
var events = new List<int[]>();
foreach (var b in buildings) {
events.Add(new int[] { b[0], -b[2] });
events.Add(new int[] { b[1], b[2] });
}
events.Sort((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
var res = new List<IList<int>>();
var heights = new SortedDictionary<int, int>();
heights[0] = 1;
int prev = 0;
foreach (var e in events) {
if (e[1] < 0) {
if (!heights.ContainsKey(-e[1])) heights[-e[1]] = 0;
heights[-e[1]]++;
} else {
heights[e[1]]--;
if (heights[e[1]] == 0) heights.Remove(e[1]);
}
int current = heights.Keys.Max();
if (current != prev) {
res.Add(new List<int>() { e[0], current });
prev = current;
}
}
return res;
}
}This code uses a priority queue (min-heap) where we push the negative of the height to simulate a max-heap, to manage the building heights efficiently. We handle start and end events separately, ensuring the heap accurately reflects the current tallest building. While processing each event, code also manages to merge the same consecutive heights, ensuring result compliance with the rules.
Time Complexity: O(N log N), where N is the number of events (two for each building).
Space Complexity: O(N), as we store up to N building heights in the heap.
Approach 2: Approach 2: Divide and Conquer
This approach involves breaking down the problem using the divide and conquer strategy. The buildings array is split into two halves recursively. The base case is a single building, where the skyline can directly be calculated. The results are then merged, taking care of overlapping heights and ensuring continuity and distinct key points.
def getSkyline(buildings):
if not buildings: return []
if len(buildings) == 1:
L, R, H = buildings[0]
return [[L, H], [R, 0]]
mid = len(buildings) // 2
Lsky = getSkyline(buildings[:mid])
Rsky = getSkyline(buildings[mid:])
return merge(Lsky, Rsky)
def merge(L, R):
h1 = h2 = 0
i = j = 0
res = []
while i < len(L) and j < len(R):
if L[i][0] < R[j][0]:
x, h1 = L[i]
i += 1
elif L[i][0] > R[j][0]:
x, h2 = R[j]
j += 1
else:
x, h1 = L[i]
_, h2 = R[j]
i += 1
j += 1
max_h = max(h1, h2)
if not res or res[-1][1] != max_h:
res.append([x, max_h])
res.extend(L[i:] or R[j:])
return resimport java.util.*;
public class SkylineDC {
public List<List<Integer>> getSkyline(int[][] buildings) {
return mergeSkyline(buildings, 0, buildings.length - 1);
}
private List<List<Integer>> mergeSkyline(int[][] buildings, int start, int end) {
if (start > end) return new ArrayList<>();
if (start == end) {
List<List<Integer>> res = new ArrayList<>();
res.add(Arrays.asList(buildings[start][0], buildings[start][2]));
res.add(Arrays.asList(buildings[start][1], 0));
return res;
}
int mid = start + (end - start) / 2;
List<List<Integer>> leftSkyline = mergeSkyline(buildings, start, mid);
List<List<Integer>> rightSkyline = mergeSkyline(buildings, mid + 1, end);
return merge(leftSkyline, rightSkyline);
}
private List<List<Integer>> merge(List<List<Integer>> L, List<List<Integer>> R) {
int h1 = 0, h2 = 0, i = 0, j = 0;
List<List<Integer>> res = new ArrayList<>();
while (i < L.size() && j < R.size()) {
int x, h;
if (L.get(i).get(0) < R.get(j).get(0)) {
x = L.get(i).get(0);
h1 = L.get(i).get(1);
i++;
} else if (L.get(i).get(0) > R.get(j).get(0)) {
x = R.get(j).get(0);
h2 = R.get(j).get(1);
j++;
} else {
x = L.get(i).get(0);
h1 = L.get(i).get(1);
h2 = R.get(j).get(1);
i++;
j++;
}
h = Math.max(h1, h2);
if (res.isEmpty() || res.get(res.size() - 1).get(1) != h) {
res.add(Arrays.asList(x, h));
}
}
res.addAll(L.subList(i, L.size()));
res.addAll(R.subList(j, R.size()));
return res;
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> mergeSkyline(const vector<vector<int>>& left, const vector<vector<int>>& right) {
int i = 0, j = 0, h1 = 0, h2 = 0;
vector<vector<int>> res;
while (i < left.size() && j < right.size()) {
int x, maxHeight;
if (left[i][0] < right[j][0]) {
x = left[i][0];
h1 = left[i][1];
++i;
} else if (left[i][0] > right[j][0]) {
x = right[j][0];
h2 = right[j][1];
++j;
} else {
x = left[i][0];
h1 = left[i][1];
h2 = right[j][1];
++i; ++j;
}
maxHeight = max(h1, h2);
if (res.empty() || res.back()[1] != maxHeight) {
res.push_back({x, maxHeight});
}
}
while (i < left.size()) {
res.push_back(left[i++]);
}
while (j < right.size()) {
res.push_back(right[j++]);
}
return res;
}
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
if (buildings.empty()) return {};
if (buildings.size() == 1) {
return { {buildings[0][0], buildings[0][2]}, {buildings[0][1], 0} };
}
int mid = buildings.size() / 2;
vector<vector<int>> left(buildings.begin(), buildings.begin() + mid);
vector<vector<int>> right(buildings.begin() + mid, buildings.end());
return mergeSkyline(getSkyline(left), getSkyline(right));
}function getSkyline(buildings) {
if (!buildings.length) return [];
if (buildings.length === 1) {
const [[left, right, height]] = buildings;
return [[left, height], [right, 0]];
}
const mid = Math.floor(buildings.length / 2);
const leftSkyline = getSkyline(buildings.slice(0, mid));
const rightSkyline = getSkyline(buildings.slice(mid));
return merge(leftSkyline, rightSkyline);
function merge(left, right) {
const res = [];
let i = 0, j = 0, h1 = 0, h2 = 0;
while (i < left.length && j < right.length) {
let x, h;
if (left[i][0] < right[j][0]) {
x = left[i][0];
h1 = left[i][1];
i++;
} else if (left[i][0] > right[j][0]) {
x = right[j][0];
h2 = right[j][1];
j++;
} else {
x = left[i][0];
h1 = left[i][1];
h2 = right[j][1];
i++;
j++;
}
h = Math.max(h1, h2);
if (!res.length || res[res.length - 1][1] !== h) {
res.push([x, h]);
}
}
res.push(...left.slice(i));
res.push(...right.slice(j));
return res;
}
}using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> GetSkyline(int[][] buildings) {
return DivideAndConquer(buildings, 0, buildings.Length - 1);
}
private List<IList<int>> DivideAndConquer(int[][] buildings, int left, int right) {
if (left > right) return new List<IList<int>>();
if (left == right) return new List<IList<int>> { new List<int> { buildings[left][0], buildings[left][2] }, new List<int> { buildings[left][1], 0 } };
int mid = (left + right) / 2;
var leftSkyline = DivideAndConquer(buildings, left, mid);
var rightSkyline = DivideAndConquer(buildings, mid+1, right);
return Merge(leftSkyline, rightSkyline);
}
private List<IList<int>> Merge(List<IList<int>> left, List<IList<int>> right) {
var result = new List<IList<int>>();
int h1 = 0, h2 = 0, idx1 = 0, idx2 = 0;
while (idx1 < left.Count && idx2 < right.Count) {
int x, h;
if (left[idx1][0] < right[idx2][0]) {
x = left[idx1][0];
h1 = left[idx1][1];
idx1++;
} else if (right[idx2][0] < left[idx1][0]) {
x = right[idx2][0];
h2 = right[idx2][1];
idx2++;
} else {
x = left[idx1][0];
h1 = left[idx1][1];
h2 = right[idx2][1];
idx1++;
idx2++;
}
h = Math.Max(h1, h2);
if (result.Count == 0 || result[result.Count - 1][1] != h) {
result.Add(new List<int> { x, h });
}
}
AddRemaining(left, idx1, result);
AddRemaining(right, idx2, result);
return result;
}
private void AddRemaining(List<IList<int>> skyline, int idx, List<IList<int>> result) {
while (idx < skyline.Count) {
result.Add(skyline[idx++]);
}
}
}This Python code uses the divide and conquer strategy where each call splits the building list into two halves and recursively solves for both sides, merging their results into a coherent skyline outline by comparing the heights at each step and ensuring the output is minimal.
Time Complexity: O(N log N), due to division of buildings and merging.
Space Complexity: O(N), needing space for recursive stack and individual skyline lists.
Approach 3: Default Approach
type Matrix struct{ left, right, height int }
type Queue []Matrix
func (q Queue) Len() int { return len(q) }
func (q Queue) Top() Matrix { return q[0] }
func (q Queue) Swap(i, j int) { q[i], q[j] = q[j], q[i] }
func (q Queue) Less(i, j int) bool { return q[i].height > q[j].height }
func (q *Queue) Push(x any) { *q = append(*q, x.(Matrix)) }
func (q *Queue) Pop() any {
old, x := *q, (*q)[len(*q)-1]
*q = old[:len(old)-1]
return x
}
func getSkyline(buildings [][]int) [][]int {
skys, lines, pq := make([][]int, 0), make([]int, 0), &Queue{}
heap.Init(pq)
for _, v := range buildings {
lines = append(lines, v[0], v[1])
}
sort.Ints(lines)
city, n := 0, len(buildings)
for _, line := range lines {
// 将所有符合条件的矩形加入队列
for ; city < n && buildings[city][0] <= line && buildings[city][1] > line; city++ {
v := Matrix{left: buildings[city][0], right: buildings[city][1], height: buildings[city][2]}
heap.Push(pq, v)
}
// 从队列移除不符合条件的矩形
for pq.Len() > 0 && pq.Top().right <= line {
heap.Pop(pq)
}
high := 0
// 队列为空说明是最右侧建筑物的终点，其轮廓点为 (line, 0)
if pq.Len() != 0 {
high = pq.Top().height
}
// 如果该点高度和前一个轮廓点一样的话，直接忽略
if len(skys) > 0 && skys[len(skys)-1][1] == high {
continue
}
skys = append(skys, []int{line, high})
}
return skys
}impl Solution {
pub fn get_skyline(buildings: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut skys: Vec<Vec<i32>> = vec![];
let mut lines = vec![];
for building in buildings.iter() {
lines.push(building[0]);
lines.push(building[1]);
}
lines.sort_unstable();
let mut pq = std::collections::BinaryHeap::new();
let (mut city, n) = (0, buildings.len());
for line in lines {
while city < n && buildings[city][0] <= line && buildings[city][1] > line {
pq.push((buildings[city][2], buildings[city][1]));
city += 1;
}
while !pq.is_empty() && pq.peek().unwrap().1 <= line {
pq.pop();
}
let mut high = 0;
if !pq.is_empty() {
high = pq.peek().unwrap().0;
}
if !skys.is_empty() && skys.last().unwrap()[1] == high {
continue;
}
skys.push(vec![line, high]);
}
skys
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sweep Line Algorithm with Priority Queue | Time Complexity: O(N log N), where N is the number of events (two for each building). |
| Approach 2: Divide and Conquer | Time Complexity: O(N log N), due to division of buildings and merging. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sweep Line with Priority Queue | O(n log n) | O(n) | Best general solution. Efficient for large building sets and the most common interview approach. |
| Divide and Conquer | O(n log n) | O(n) | Useful when modeling the skyline merge process or applying merge-sort style recursion. |
Frequently asked questions
Is The Skyline Problem easy or hard?
The Skyline Problem is classified as Hard because it combines multiple concepts: event sorting, heap management, and careful handling of overlapping intervals. Implementing the sweep line logic without producing redundant points requires careful reasoning.
How to solve The Skyline Problem in O(n)?
An exact O(n) algorithm generally isn't feasible because building edges must be processed in sorted order. Sorting alone requires O(n log n) time in comparison-based models. The practical optimal approach is O(n log n) using a sweep line with a max heap or a divide and conquer skyline merge.
What is the best approach for The Skyline Problem?
The sweep line algorithm with a priority queue is the most widely used solution. Convert building edges into start and end events, sort them by x-coordinate, and track active heights using a max heap. Whenever the maximum height changes, record a new skyline key point. This approach runs in O(n log n) time and O(n) space.
Is The Skyline Problem asked at Google/Amazon/Meta?
The Skyline Problem appears frequently in interviews at large tech companies including Google, Amazon, and Meta. It tests understanding of sweep line algorithms, heaps, and interval merging. Variants of skyline or silhouette problems are commonly used to evaluate algorithmic reasoning.
What data structure is used in The Skyline Problem?
The primary data structure is a max heap (priority queue) that stores active building heights during the sweep line traversal. Other implementations may use balanced ordered sets, segment trees, or binary indexed trees to manage height ranges efficiently.
What is the time complexity of The Skyline Problem?
Most optimal solutions run in O(n log n) time. Sorting building edges requires O(n log n), and each heap insertion or removal during the sweep line process costs O(log n). The overall space complexity is typically O(n) to store events, the heap, and the resulting skyline points.
The Skyline Problem Python or Java solution approach?
Most Python and Java implementations follow the sweep line pattern. Convert each building into two events, sort the events, and use a priority queue to maintain active heights. Each time the maximum height changes, append a new skyline key point to the result.