FAANG · LeetCode #218

The Skyline Problem — three-stage drill

1The ProblemHard

The Skyline Problem

Trace the silhouette of a city of overlapping buildings — return the key (x, height) points where the outline changes.

Examples

[[2,9,10],[3,7,15],[5,12,12]]→ [[2,10],[3,15],[7,12],[12,0]][[0,2,3],[2,5,3]]→ [[0,3],[5,0]]

constraintOutput is a list of [x, h] key points marking where the silhouette height changes. The last point has height 0.

2The PatternTIME O(n log n) · SPACE O(n)

Intervals

Given a pile of ranges, sort them by start — now any overlap is a neighbour, so a single left→right pass handles them.

Problems using this pattern

3The SolutionRESULT → [[2,10],[3,15],[7,12],[12,0]]

Step through it

given: 3 buildings · trace the silhouette (skyline)

Step 1 / 8

Python▎events · sort · running max via heap · emit on change

1import heapq
2 
3def getSkyline(buildings):
4    events = []
5    for L, R, H in buildings:
6        events.append((L,  -H, R))   # enter — negative H so max-heap via min-heap
7        events.append((R,    0, 0))  # leave — placeholder, heights expire by R
8    events.sort()
9 
10    out = []
11    heap = [(0, float('inf'))]       # (−height, expiry)
12    for x, negH, R in events:
13        if negH:                     # enter event
14            heapq.heappush(heap, (negH, R))
15        # lazy-delete: pop heights whose building has ended at or before x
16        while heap[0][1] <= x:
17            heapq.heappop(heap)
18        h = -heap[0][0]
19        if not out or out[-1][1] != h:
20            out.append([x, h])
21    return out

why it worksConvert every building into two events on the x-axis: a LEFT (height enters) and a RIGHT (height leaves). Sort events left→right (enters before leaves on ties so a back-to-back pair doesn't dip to 0). Sweep, keeping a multiset of currently-active heights. After each event, the current skyline height is just the max of that set. If the max changed compared to before, emit a key point at (event.x, newMax). The active set is usually a max-heap (with lazy deletion), but the geometric idea is the picture above — the heap is just bookkeeping. O(n log n).

The Skyline Problem — three-stage drill