Sweep Line Algorithms: A Practical Guide for Coding Interviews
3 views
Sweep line is one of those techniques that sounds academic but shows up constantly in real interview loops. Any time a problem talks about intervals, events on a timeline, rectangles on a plane, or "at any moment, how many...", there is a good chance the clean solution is to sort events and sweep across them once.
The mental model
Imagine a vertical line moving left to right across your data. You only care about the moments when something changes: an interval starts, an interval ends, a building begins or stops. Turn each of those moments into an event, sort the events, and process them in order while maintaining some state (a counter, a heap, a balanced tree). Everything between two events is static, so you never need to look at it.
Template
events = []
for start, end in intervals:
events.append((start, +1))
events.append((end, -1))
events.sort()
active = best = 0
for x, delta in events:
active += delta
best = max(best, active)
The sort order matters. Because (end, -1) sorts before (start, +1) at the same x, a meeting that ends at 10 and another that starts at 10 do not overlap. If the problem treats touching intervals as overlapping, flip the tie-break. Saying this out loud is an easy way to show care.
Classic interview problems
- Meeting Rooms II: minimum number of rooms equals the peak value of "active". You can also solve it with a min-heap of end times; mention both and compare.
- Employee Free Time: merge everyone's busy intervals with a sweep, and the gaps between merged blocks are the free time.
- The Skyline Problem (LeetCode 218): events are building edges; the state is a max-heap (or sorted multiset) of active heights. Each time the maximum changes, emit a key point. This is the problem where interviewers really test whether you understand lazy deletion from a heap.
- Rectangle Area II: sweep across x, and at each slab compute the covered length on the y-axis, often with a segment tree over compressed y-coordinates.
- My Calendar series: an online version where events arrive one at a time; a sorted map of deltas keeps the sweep incremental.
Complexity
Sorting dominates: O(n log n). The sweep itself is O(n) for a counter, or O(n log n) when the state is a heap or tree. Coordinate compression keeps memory proportional to the number of events, not the coordinate range.
How to talk through it
1. Restate the problem as events on an axis.
2. Decide what each event changes and what state you need.
3. Nail the tie-breaking rule with a tiny example.
4. Code it, then test the edge cases: empty input, identical intervals, nested intervals, touching endpoints.
Interviewers usually care less about whether you have memorized the skyline problem and more about whether you can turn a messy word problem into events. Practicing that translation out loud is what pays off. If nerves make you lose your thread in the moment, Linkjob AI (https://linkjob.ai) provides real-time help during live job interviews and technical interviews, so you can keep your reasoning structured while you code.