Understanding the line sweep technique for points

The line sweep technique efficiently solves most problems where events can be marked on an axis of the cartesian plane. These events don't necessarily have to be intervals but can also be individual points representing some scalar value. For many interval problems, we use the start and end coordinates of an interval as individual points on an axis and use the line sweep algorithm of these points.

Line sweep technique

The basic idea remains the same when using the line-swept technique on points instead of intervals. We first arrange the points in some order and  "sweep" a line across the set of points while maintaining a data structure that keeps track of the current state. Let's understand how the line sweep technique can be applied to points.

1. Convert intervals to points

If given an array of intervals instead of points, we split each interval into two points, start and end, and create a new array of points to operate on instead of the array of intervals.

2. Sort the points

The next step is to sort the points, as the line sweep algorithm requires the events to be sorted in some order in the array holding them. This way, the array can be viewed as the x-axis of the cartesian plane with points marked on it from left to right. This allows us to traverse the array as if we were swiping a line through it on the x-axis of the cartesian plane.

Points are generally sorted in a non-decreasing order of their values and clearly labeled as a start or end point. If a start and end point has the same value, we generally keep the end point before the start point, however the order may be different for different problems.

3. Sweep the line

Once we have sorted the array of intervals, traversing it from start to end becomes the same as moving on the x-axis from left to right. We keep some data structure like an event counter, set, or list to keep state information as we traverse the array from start to end. This can be visualized as a vertical line moving from left to right on the x-axis and hence is called a line sweep. As the sweep line moves, it dynamically updates the state variables to correctly process overlaps, merges, or other conditions dictated by the problem.

Complexity Analysis

The sweep line algorithm on points splits each interval in the interval array into points, and then sort it which takes O(NlogN) time, where N is the size of the array. We traverse the array of points only once in linear O(N) time, and so the time complexity in any case is O(NlogN).

If we are given an array of intervals instead of points, we will have to split it, for which we create a separate array of size 2*N, and so the space complexity will be linear O(N). In other cases, we may be able to sort the input array without creating any additional data structure and have a constant O(1) space complexity.

Best Case: Given array of points

• Space Complexity - O(1)
• Time Complexity - O(NlogN)

Worst Case: Given array of intervals

• Space Complexity - O(N)
• Time Complexity - O(NlogN)