Line Sweep Problems
6 Line Sweep LeetCode problems · Browse tasks by difficulty and choose your next practice problem.
Learn the coding interview patterns behind these problems.
Turn geometric changes into ordered events
A sweep processes coordinates in sorted order and maintains the state between adjacent event positions. Interval coverage needs an active count; skyline height needs an ordered multiset; rectangle union area needs the covered length on the other axis. The event order is only half the solution: choose state that answers the actual question.
When to use it
Use a sweep when the answer changes only at interval endpoints, rectangle edges, or sorted query positions. Offline interval queries can often share one sweep rather than re-scanning every interval for each query.
Worked example
Find the union length of half-open intervals [1, 4), [2, 5), and [5, 6).
- Create +1 events at starts and -1 events at ends. Sort and group events at the same coordinate.
- The active counts on [1, 2), [2, 4), [4, 5), and [5, 6) are 1, 2, 1, and 1.
- Add each gap's length once whenever its active count is positive: 1 + 2 + 1 + 1.
The union length is 5. The end and start at coordinate 5 create no gap or double-counted length.
Time and space
For n intervals, sorting 2n events takes O(n log n) time and the scan takes O(n), with O(n) event storage. More complex sweeps add the cost of their active-set operations; a count alone cannot maintain rectangle union length.
Mistakes to check
- Specify closed versus half-open endpoints. Group equal-coordinate events before producing a new skyline segment or advancing to the next gap.
- Duplicate heights require multiplicities: removing one building must not remove another active building of the same height.
- Coordinate compression preserves ordering, not distance. Compute lengths from original coordinate differences, not compressed index differences.
Further reading: Princeton Algorithms: geometric intersections and sweep lines
Guide reviewed .