The Skyline Problem
Hard · Trees · Array · Divide and Conquer · Heap (Priority Queue) · Sweep Line · Ordered Set
Problem
A city skyline is the outer contour formed by all of its buildings seen from far away. Each building is a rectangle standing on flat ground at height 0, given as buildings[i] = [left_i, right_i, height_i]: it covers left_i <= x < right_i.
Return the skyline as a list of key points [x, y] sorted by x. Each key point is the left end of a horizontal segment of the contour, and the last key point always has y = 0, marking where the rightmost building ends. Stretches of ground between buildings are part of the contour.
The output must not contain two consecutive key points at the same height: [[2,3],[4,5],[7,5],[11,5],[12,7]] is invalid and should be [[2,3],[4,5],[12,7]].
Examples
Input: buildings = [[1,4,6],[2,6,3],[8,10,5]] Output: [[1,6],[4,3],[6,0],[8,5],[10,0]]
The tall building ends at 4, dropping to the shorter one until 6, then there is a gap before 8.
Input: buildings = [[0,3,4],[3,5,4]] Output: [[0,4],[5,0]]
The two buildings touch at the same height, so they merge into one segment.
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]]
The 15-tall building rises inside the first one; when it ends at 7, the 12-tall one is the tallest left.
Constraints
- 1 <= len(buildings) <= 10^4
- 0 <= left_i < right_i <= 2^31 - 1
- 1 <= height_i <= 2^31 - 1
- buildings is sorted by left_i in non-decreasing order
Approaches
- Check every building at every edge — time O(n²), space O(n)
Follow-up
Can you avoid the heap? Divide and conquer works like merge sort: split the buildings in half, compute each half’s skyline, then merge the two key-point lists with two pointers, tracking the current height of each side and emitting max(left, right) whenever it changes. The merge is linear, so the whole thing is O(n log n) without any priority queue.
Related problems
Start free on Cariara · Coding problems · System design studio
