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.

💡 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:

1. Move left while the ground keeps getting lower; if it reached a lower point, settle there.
2. Otherwise try the same to the right.
3. 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

1. Sort the events, then walk them. That is the whole sweep-line technique.
2. Emit on change, not on event — it removes an entire post-processing step.
3. Lazy deletion substitutes for a removal a heap does not have.
4. Negating heights buys two things at once: max-heap behaviour and correct same-x ordering.
5. A sentinel keeps the structure non-empty and makes the boundary case disappear.
6. State a simulation's rule exactly before coding it. Ambiguity there is the bug.
7. 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.