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, and a binary heap cannot do that. The fix is lazy deletion: when a building ends, only count its height as dead, and pop a dead height later, when it reaches the top of the heap. The answer is correct whenever you read the top, because you clean the top first.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core 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)) # enter: negative height sorts tallest first
events.append((r, h)) # leave: positive, sorts after every enter at this x
events.sort()
res, live, dead = [], [0], defaultdict(int) # live: negated heights, 0 is the ground
i = 0
while i < len(events):
x = events[i][0]
while i < len(events) and events[i][0] == x: # take every event at this x first
e = events[i][1]
if e < 0: heappush(live, e)
else: dead[e] += 1 # lazy delete: count it, do not remove it
i += 1
while live[0] and dead[-live[0]]: # clean the top before reading it
dead[-live[0]] -= 1; heappop(live)
h = -live[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 also make taller buildings sort before shorter ones at the same x, which matters when two buildings start together. The ground entry 0 means the heap is never empty, so 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.
At a shared x, enters sort before leaves, because a negative number sorts before a positive one. That keeps the height flat when one building ends exactly where an equal-height one begins. The code also handles every event at an x before it reads the heap. Tie ordering is the crux of this problem.
2. The simulation
Pour Water has no structure to choose. Each drop follows one rule:
- Move left while the next cell is flat or lower; if it reached a cell strictly lower than where it fell, settle at the lowest such cell.
- 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. Among equally low cells it takes the one nearest to where it fell, and the left side is always tried before the right. 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]]
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
- Peak concurrency. "How many things are active at time x" is the same sweep with counts instead of heights: sort start and end events and keep a running total.
- Calendar and capacity views. The busiest moment of a day is a sweep over start and end events.
- Falling-sand style simulations. A rule applied to one particle at a time, where the rule's tie-breaks decide the result, is the shape of Pour Water.
5. Problems in this chapter
The Skyline Problem
Outline of a set of overlapping rectangles. Sort enter and leave events, keep a max-heap of live heights with lazy deletion, and emit only when the top changes. Enters sort before leaves at the same x, and taller enters come first.
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 rolls over flat or downhill cells to the lowest cell it can reach, tries left before right, and rests where it fell if nothing is strictly lower. For [3,1,3] with 5 drops at index 2 the drops land at 1, 1, 2, 1, 0 and the result is [4,4,4].
Pattern: rule-exact simulation. Target: O(drops × width) time, O(n) space for a copied array (O(1) extra if you mutate in place).
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. At a shared x, enters come before leaves, and taller enters come first. Process all events at an x before reading the heap.
- Letting a water drop travel uphill to reach a lower point further along. It may not.
- Breaking the water tie-break wrongly. Left is tried first, and among equally low cells the one nearest to the drop wins.
7. Key takeaways
- Sort the events, then walk them. That is the whole sweep-line technique.
- Emit on change, not on event, which removes an entire post-processing step.
- Lazy deletion substitutes for a removal a heap does not have. Count the height as dead and pop it when it surfaces.
- 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 ask it: both problems are mostly bookkeeping, and the bugs are in tie-breaks.
Order: The Skyline Problem → Pour Water.
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