Sweep Line Technique
A powerful algorithmic strategy to solve geometry and range problems by simulated scanning.
Scanning the Plane
As the line (blue) moves, it counts how many intervals are currently "active" (intersecting the line).
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Instead of checking every possible coordinate or point in a 2D plane, imagine a vertical line sweeping across the plane from left to right.
We only stop at "interesting" points (Events). By processing events in sorted order, we can maintain the state of the active elements efficiently.
Concept
Key Components:
- Events: Points where status changes (Start of interval, End of interval, Intersection point).
- Event Queue: A sorted list of all future events.
- Active Set (State): Data structure tracking currently active objects intersecting the sweep line (e.g., BST, Scalar Count).
How it Works
The visualizer shows the line moving across intervals.
- Start Event: Add interval to active set.
- End Event: Remove interval from active set.
- Query: At any point, the active set tells us how many intervals overlap.
Step-by-Step Breakdown
1. Decompose objects into Events (Start/End).
2. Sort Events by coordinate (usually X).
3. Iterate through sorted events.
4. Update Active Set based on event type.
When to Use
- Finding overlapping intervals.
- Closest Pair of Points.
- Union of Rectangles Area.
- Convex Hull construction.
When NOT to Use
- When objects are not static (dynamic updates).
- When dimensions are higher than 2D (gets complex fast).
How to Identify
"Overlapping rectangles", "Interval intersection", "Points in plane".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.