← DSA Atlas
Dedicated problem page · #218

The Skyline Problem

HardAdvanced Range Data StructuresSweep line with max-heapPriority queue over building edges
Solve on LeetCode ↗
218
HardAdvanced Range Data StructuresPriority queue over building edgesSweep line with max-heap

The Skyline Problem

Given a list of buildings, each described as [left, right, height], compute the skyline: the outer contour formed by all buildings viewed from a distance. Return it as a list of key points [x, height] sorted by x, where each point marks the left endpoint of a horizontal segment. The last point has height 0 to close the skyline, and no two consecutive segments may share the same height.

Open official problem prompt ↗
In plain English

Produce the outline of a city skyline: the sequence of x positions where the visible top height changes as you scan across all overlapping buildings.

Picture it like this

Imagine walking east past a row of buildings and continuously noting the height of the tallest one blocking the sky. Each time that tallest silhouette changes, you jot down where and how high — that log is the skyline.

Example
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]]
Why
The tallest active building at each x sets the height; the contour rises to 15 at x=3, drops as buildings end, and returns to 0 at x=12 and x=24.
Constraints
1 <= buildings.length <= 10^40 <= left < right <= 2^31 - 11 <= height <= 2^31 - 1buildings is sorted by left in non-decreasing order
Pattern lesson

See the pattern, then code

Sweep line with max-heap
Recognition clue

You must track the maximum of a set of overlapping intervals as a horizontal sweep crosses their start and end edges — a classic sweep line plus max-structure signal.

↗
Advanced Range Data Structures

Online prefix or range queries with updates, inversions, or coordinate compression.. Only the tallest currently-active building matters at any x. Convert each building into a start edge and an end edge, sweep left to right, keep active heights in a max-heap, and emit a key point whenever the max height changes.

New words, made simpleKnow these before the algorithm
Sweep line
An imaginary vertical line moving left to right, stopping at each interesting x-coordinate (a building edge).
Key point
An [x, height] pair marking where a new horizontal segment of the skyline begins.
Lazy deletion
Leaving stale entries in the heap and discarding them only when they surface at the top, since heaps cannot remove arbitrary elements cheaply.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute force per x

Coordinates can reach 2^31, so scanning every x is hopelessly slow.

For every integer x-coordinate, scan all buildings to find the tallest covering it.

Time O(n * W)Space O(1)
Best choiceSweep line + max-heap

Processes only 2n events and answers the tallest-active query in log time.

Turn buildings into edge events, sweep across them, and keep active heights in a max-heap so the current tallest is always available.

Time O(n log n)Space O(n)
The rule we keep true

Invariant

After processing all events at coordinate x, the heap top equals the height of the tallest building whose interval covers x (or 0 if none), so the emitted contour is always correct up to x.

Why this is correct

Reasoning

Sorting starts before ends and taller starts first guarantees that when two events share an x, the resulting max height is computed after all relevant changes. Lazy popping removes only buildings that have truly ended (right <= x), so the heap top faithfully reflects the current maximum, and we emit a point exactly when that maximum changes.

The algorithm in three movesSay these aloud before coding
1Split each building into a start event (x=left, height, right) and an end event (x=right)

x=2: heap={10}, emit [2,10]

2Sort all events by x, processing taller starts before shorter ones at the same x

x=3: heap={15,10}, emit [3,15]

3Lazily pop heap entries whose right end is at or before the current x

x=7: pop 15, heap={12,10}, emit [7,12]

4Push each start's (negative height, right) so the heap top is the tallest active building

5When the current max height differs from the last emitted height, append [x, maxHeight]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
s2:100
s3:151
e72
e93
s5:124
s15:105
e126
s19:87
e208
e249
1 · Readevent (2, -10, 9)
2 · AskDoes the max height change?
3 · Update stateheap = {10}
4 · ResultMax goes 0 -> 10, emit [2,10]
Key takeaway

Events sorted by x; at x=3 the height-15 building becomes the tallest active building, raising the skyline.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5-8Build events

    Each building yields a start (negative height so heapq sorts tallest first, carrying its right end) and an end marker at its right edge.

  2. 2
    Lines 9Sort events

    Sorting by (x, -height) makes taller starts win ties and start events precede end events at the same x.

  3. 3
    Lines 11Heap sentinel

    Seeding (0, inf) means the heap is never empty, so the ground level 0 is always the fallback height.

  4. 4
    Lines 13-14Lazy expiry

    Discard heap entries whose right end has been reached before reading the current max.

  5. 5
    Lines 17-19Emit on change

    Only record a key point when the tallest height differs from the last one, avoiding duplicate flat segments.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single building returns [[left,h],[right,0]]
  • Buildings sharing the same left edge (taller must be processed first)
  • Adjacent buildings of equal height that touch at an edge must not create a spurious point
  • Fully nested buildings where a shorter one is entirely inside a taller one produces no visible change
!

Common beginner mistakes

  • Forgetting to negate heights and getting a min-heap instead of a max-heap
  • Popping by height instead of by right-end coordinate, deleting a still-active building
  • Emitting a point even when the max height is unchanged, violating the no-consecutive-equal rule
  • Mishandling ties: an end at x and a start at x with equal heights must not drop the contour to 0 momentarily
Check your understanding

Why do we store the right end in the heap alongside the negative height, and pop by right end rather than by height?

More in Advanced Range Data Structures

#307Range Sum Query – MutablePoint update, prefix-sum query#315Count of Smaller Numbers After SelfCount smaller to the right#327Count of Range SumCount prefix-sum pairs in range#493Reverse PairsCount significant inversions#699Falling SquaresRange assign, range max#715Range ModuleMerge and split disjoint intervals