The sweep line technique processes events in sorted order along a dimension (typically time or position). It converts 2D problems into 1D by “sweeping” a line across the input and maintaining state about what the line intersects. This guide covers the sweep line patterns that appear in coding interviews — from meeting room scheduling to the skyline problem.
The Sweep Line Concept
The core idea: decompose intervals or rectangles into events (start/end points), sort events by position, and process them left to right while maintaining a data structure tracking the current state. For intervals [start, end]: create two events: (+1 at start, -1 at end). Sort events by position. Scan left to right, maintaining a running count. The count at any position tells you how many intervals overlap at that point. This is the difference array technique applied to continuous ranges. Time: O(N log N) for sorting. The sweep line transforms questions about overlapping intervals into questions about event processing, which are often easier to solve.
Pattern 1: Maximum Overlap (Meeting Rooms)
Meeting Rooms II: find the minimum number of meeting rooms needed. Decompose each meeting [start, end) into two events: +1 at start (a room is needed), -1 at end (a room is freed). Sort all events by time. If two events have the same time, process the end event first (a room freed at time T can be reused for a meeting starting at T). Scan through events, maintaining a running count (current rooms in use). The maximum count is the answer. Time: O(N log N). This is equivalent to the min-heap approach but conceptually simpler. Variations: (1) Maximum concurrent users online (same pattern — user login = +1, logout = -1). (2) Maximum bandwidth usage at any point (each transfer uses bandwidth during [start, end]). (3) Minimum platforms at a train station (arrival = +1, departure = -1). All follow the same pattern: decompose into events, sort, sweep, track the maximum.
Pattern 2: The Skyline Problem
Given buildings as [left, right, height] rectangles, compute the skyline (the outline when viewing all buildings from the front). This is one of the hardest sweep line problems. Approach: create events for each building: (left, -height) for building start and (right, height) for building end. Negative height for starts ensures that when two events have the same x-coordinate, taller buildings are processed first. Sort events by x-coordinate. Maintain a max-heap (or sorted multiset) of active building heights. At each event: if it is a start event, add the height to the heap. If it is an end event, remove the height from the heap. After processing each event, check if the current maximum height changed. If it did, add (x, current_max_height) to the result. Time: O(N log N) with a balanced BST or sorted multiset. With a lazy-deletion heap: O(N log N) amortized. Key insight: the skyline changes only when the maximum active height changes. The heap efficiently tracks the current maximum among all active buildings.
Pattern 3: Interval Scheduling with Sweep Line
Car Pooling: given trips [passengers, start, end], determine if a car with capacity C can serve all trips without exceeding capacity. Events: +passengers at start, -passengers at end. Sort, sweep, check if the running total ever exceeds C. Time: O(N log N). Corporate Flight Bookings: N flights and booking ranges [first, last, seats]. Find total seats booked for each flight. This is the difference array: add +seats at first, -seats at last+1. Compute prefix sum. Time: O(N + K) where K is the number of bookings. My Calendar I/II/III: a series of calendar problems where you add events and check for overlaps. My Calendar I: no double booking allowed. My Calendar II: allow at most 2 overlapping. My Calendar III: return the maximum overlap (K-booking). All solvable with the sweep line event approach: maintain a sorted map of events, query the max overlap count. Range coverage: given intervals, find the total length covered (merge overlapping intervals, sum lengths) or the number of points covered by at least K intervals (sweep line with a counter, sum ranges where counter >= K).
Pattern 4: Line Sweep in 2D
Some problems require sweeping in 2D: Rectangle Area II: given axis-aligned rectangles, find the total area covered (union of rectangles). Sweep a vertical line from left to right. At each x-event (rectangle start or end), update the set of active rectangles. The covered height at each x is the union of active rectangle y-ranges (computed with a segment tree or merge). The area between consecutive x-events = covered_height * (x2 – x1). Time: O(N^2) or O(N log N) with a segment tree. Count points in rectangles: given points and rectangle queries, count points inside each rectangle. Sweep by x-coordinate. For each rectangle, at x_left add it to the active set, at x_right remove it. Use a BIT (Fenwick tree) on the y-coordinate to count points. Coordinate compression: when coordinates are large but sparse, map them to consecutive integers. N rectangles have at most 2N unique x-coordinates and 2N unique y-coordinates. Compress to indices 0..2N-1. This makes array-based data structures feasible.
When to Use Sweep Line
Recognition signals: (1) “Maximum overlap” or “minimum resources for concurrent events” -> sweep line with +1/-1 events. (2) “Total area/length covered by intervals/rectangles” -> sweep line with merge. (3) “Skyline” or “outline of overlapping shapes” -> sweep line with max-heap. (4) “Range addition on an array” -> difference array (discrete sweep line). (5) Anything involving “at time T, how many X are active?” -> sweep line. The sweep line reduces interval problems to event processing: sort events, maintain state, query state at each event. The state data structure varies: a simple counter (meeting rooms), a heap (skyline), a segment tree (2D area), or a sorted map (calendar). Practice problems in order: Meeting Rooms II (easy sweep), Car Pooling (easy), My Calendar III (medium), Skyline Problem (hard), Rectangle Area II (hard). The first three build intuition; the last two test advanced data structure integration.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How does the sweep line technique work for interval problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The sweep line decomposes intervals into events and processes them in sorted order. For each interval [start, end]: create +1 event at start and -1 event at end. Sort all events by position (break ties: end events before start events at the same time). Scan left to right maintaining a running counter. The counter at any point equals the number of overlapping intervals. This transforms 2D overlap questions into 1D event processing. Time: O(N log N) for sorting. Applications: Meeting Rooms II (maximum simultaneous meetings = peak counter value), car pooling (check if passenger count exceeds capacity), maximum concurrent users, and minimum platforms at a train station. All follow the same pattern: decompose, sort, sweep, track the maximum.”}},{“@type”:”Question”,”name”:”How does the skyline problem use sweep line with a heap?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Given buildings [left, right, height], compute the outline. Create events: (left, -height) for start, (right, height) for end. Negative height for starts ensures taller buildings process first at the same x. Sort by x-coordinate. Maintain a max-heap of active building heights. At each event: start event adds height to heap, end event removes it. After each event, check if the current maximum height changed. If yes, add (x, new_max) to the skyline result. The skyline changes only when the maximum active height changes. Time: O(N log N) with a balanced BST or sorted multiset for the active heights. This is one of the hardest sweep line problems — practice Meeting Rooms II first to build intuition.”}},{“@type”:”Question”,”name”:”What is the difference between sweep line and difference array?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”They are the same concept applied differently. Difference array: for discrete positions (array indices). Add +V at position left, -V at position right+1. Compute prefix sum to get the final array. O(N + Q) for Q range updates on array of size N. Sweep line: for continuous or large coordinate spaces. Create events at interval start/end points, sort them, process in order. O(N log N) due to sorting. Use difference array when: coordinates are small integers and you need the value at every position (flight bookings, range addition). Use sweep line when: coordinates are large or continuous, you only need the value at event points (meeting rooms, skyline), or events have different types (building start/end with heights). The sweep line is the generalization; the difference array is the special case for integer coordinates.”}},{“@type”:”Question”,”name”:”When should you recognize a problem needs sweep line?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Recognition signals: (1) Maximum overlap or minimum resources for concurrent events -> sweep line with +1/-1 events. (2) Total area or length covered by intervals/rectangles -> sweep line with merge. (3) Skyline or outline of overlapping shapes -> sweep line with max-heap. (4) Range additions on an array -> difference array (discrete sweep line). (5) At time T, how many X are active? -> sweep line. Practice order: Meeting Rooms II (basic sweep), Car Pooling (sweep with capacity check), My Calendar III (sweep with sorted map), Skyline Problem (sweep with heap), Rectangle Area II (2D sweep with segment tree). The first two problems build core intuition; the rest test advanced data structure integration.”}}]}