Geometry and Sweep
What is this?
The Skyline Problem is the canonical sweep: sort every place where something changes, walk them in order, and keep a structure describing what is currently active. The output is emitted whenever that structure's summary changes.
Pour Water is the opposite temperament — a simulation with no data structure at all, where every difficulty is in stating the settling rule precisely enough to implement.
never uphill"]
💡 Fun fact: the skyline sweep needs a max-heap that supports removing an arbitrary building when its right edge passes — an operation heaps do not have. The fix is the same lazy deletion used for priority queues with changing keys: push
(−height, right_edge)and, before reading the top, discard any entry whose right edge is at or behind the current x. Entries die when they surface, not when they expire, and the answer is always correct at the moment it is read. The same trick appears in three separate chapters of this tier, which is a good reason to learn it once and properly.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
The one-line idea: sort the events, keep a structure of what is live, and emit only when the summary changes. A sweep that emits on every event is not wrong so much as unreadable.
1. The sweep
events = []
for l, r, h in buildings:
events.append((l, -h, r)) # left edge: negative height sorts tallest first
events.append((r, 0, 0)) # right edge: a marker, no height
events.sort()
res, live = [], [(0, float('inf'))] # (−height, right edge); ground never expires
for x, negh, r in events:
while live[0][1] <= x: heappop(live) # lazy expiry
if negh: heappush(live, (negh, r))
h = -live[0][0]
if not res or res[-1][1] != h: res.append([x, h])
Three details do all the work. Negative heights make a min-heap behave as a max-heap and simultaneously make taller buildings sort before shorter ones at the same x — which matters when two buildings start together. The ground sentinel (0, ∞) means the heap is never empty and the height falls to 0 naturally at the end of a run. And emitting only on change removes every duplicate point without a post-processing pass.
Right edges must be processed before left edges at the same x when the buildings do not overlap — which the (x, 0, 0) tuple gives for free, since 0 sorts after any negative height.
2. The simulation
Pour Water has no structure to choose. Each drop follows one rule:
- Move left while the ground keeps getting lower; if it reached a lower point, settle there.
- Otherwise try the same to the right.
- Otherwise settle where it fell.
"Keeps getting lower" is the part to state carefully — the drop may cross flat ground on its way to a lower point, but it may never go up, and it settles at the lowest position it can reach, breaking ties toward the left. Getting that ordering wrong produces plausible-looking output that is wrong on ridges and plateaus, which is exactly what the test cases probe.
3. A 30-second worked example (skyline)
buildings = [[2,9,10], [3,7,15], [5,12,12]]
events sorted: (2,-10,9) (3,-15,7) (5,-12,12) (7,0,0) (9,0,0) (12,0,0)
x=2 push (-10, 9) live top = 10 ≠ nothing emit [2, 10]
x=3 push (-15, 7) live top = 15 ≠ 10 emit [3, 15]
x=5 push (-12, 12) live top = 15 == 15 no emit
x=7 expire (-15, 7) live top = 12 ≠ 15 emit [7, 12]
x=9 expire (-10, 9) live top = 12 == 12 no emit
x=12 expire (-12,12) live top = 0 ≠ 12 emit [12, 0]
skyline: [[2,10], [3,15], [7,12], [12,0]]
Two events emit nothing. At x=5 a new building starts but is hidden behind a taller one, and at x=9 a building ends without changing the visible height. Those are the two cases the "emit only on change" rule exists for — a sweep that appends unconditionally produces six points where four are correct.
4. Where you'll actually meet this
- Graphics and rendering. Silhouette and occlusion computation is the skyline problem in two dimensions.
- Resource utilisation charts. "How many things are active at time x" is the same sweep with counts instead of heights.
- GIS and mapping. Horizon lines and viewshed analysis over elevation data.
- Terrain and hydrology. Water settling models are Pour Water with more physics and the same logic.
- Calendar and capacity views. Peak concurrent usage over a day is a sweep over start and end events.
5. Problems in this chapter
▶ The Skyline Problem
Outline of a set of overlapping rectangles. Sweep sorted edges with a max-heap of live heights, expiring entries lazily, and emit only when the height changes.
Pattern: sweep line + heap with lazy deletion. Target: O(n log n) time, O(n) space.
▶ Pour Water
Simulate water drops settling on a terrain. Each drop moves to the lowest reachable position, preferring left, never travelling uphill.
Pattern: rule-exact simulation. Target: O(drops × width) time, O(1) extra space.
6. Common pitfalls 🚫
- Emitting a point at every event, which duplicates heights and fails the exact-output requirement.
- Using positive heights in the heap, which gives a min-heap when a max-heap is needed and breaks same-x ordering.
- Omitting the ground sentinel, so the heap empties and the final drop to zero is missed.
- Trying to remove a specific building from the heap. Expire lazily on the way out.
- Mis-ordering equal x-coordinates. Taller left edges must come first; right edges must come after.
- Letting a water drop travel uphill to reach a lower point further along. It may not.
- Breaking the water tie-break rightward. Left is preferred, and the tests check it.
7. Key takeaways
- Sort the events, then walk them. That is the whole sweep-line technique.
- Emit on change, not on event — it removes an entire post-processing step.
- Lazy deletion substitutes for a removal a heap does not have.
- Negating heights buys two things at once: max-heap behaviour and correct same-x ordering.
- A sentinel keeps the structure non-empty and makes the boundary case disappear.
- State a simulation's rule exactly before coding it. Ambiguity there is the bug.
- Why interviewers like it: the skyline is a well-known hard problem where the difficulty is entirely in the bookkeeping, which is where real code goes wrong too.
Order: The Skyline Problem → Pour Water.
The Skyline Problem
Core idea: A city is a pile of overlapping rectangles, and the skyline is the upper outline you'd photograph from far away — the silhouette of the union of those rectangles. The trick that tames it is to stop thinking about rectangles and start thinking about a vertical sweep line gliding left to right. As the line moves, the only thing you care about is the tallest building currently under it — that height is the skyline at that x. The height can only ever change at a building's left edge (a new building joins, possibly lifting the line) or its right edge (a building leaves, possibly dropping the line). So you don't sweep continuously; you jump from edge to edge. Turn each building
[L, R, H]into two events — an enter atx = Land a leave atx = R— sort all events by x, and maintain a max-heap of active heights. At each x, the heap top is the current skyline height; whenever that top changes from the previous one, you emit a key point[x, newMax]. Removing a leaving building from the middle of a heap is awkward, so use lazy deletion: mark it dead in a counter and only actually pop it once it bubbles to the top. The one genuinely subtle part is event ordering at a shared x — getting "a taller building entering exactly where another leaves" right — which we encode so the tuple sort handles it for free. Sort dominates: O(n log n).
The problem, rephrased
Imagine you're standing far across the river photographing a city at dusk. Every building is a plain rectangle sitting on the ground — you're given each as [left, right, height]. Buildings overlap, hide behind one another, and butt up against each other. What your camera captures is just the outline of their combined shape: a staircase of horizontal segments where the height of the tallest building in front determines the roofline, dropping to the ground in the gaps.
You don't want to draw every pixel of that outline — you want its corners: the (x, height) points where the roofline changes level. Read those key points left to right and you can reconstruct the whole silhouette by drawing a flat line at each height until the next point.
Formally — this is LeetCode 218 — The Skyline Problem: given buildings, a list of [left, right, height], return the skyline as a list of key points [x, height] sorted by x. Each key point marks the left endpoint of a horizontal segment of the outline. The last point always has height 0 (the right end of the rightmost building, where the city meets the ground). Consecutive segments must have different heights — no redundant points.
| Input | Means | Output |
|---|---|---|
[[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]] |
five overlapping towers | [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]] |
[[0,2,3],[2,5,3]] |
two equal-height buildings sharing an edge | [[0,3],[5,0]] (one merged segment) |
[[1,5,3]] |
a single building | [[1,3],[5,0]] (up at left, down at right) |
The interesting word is outline — the answer is not the buildings, it's the boundary of their union, and that boundary only turns at building edges.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson