You are given a 0-indexed 2D integer array nums representing the coordinates of the cars parking on a number line. For any index i, nums[i] = [starti, endi] where starti is the starting point of the ith car and endi is the ending point of the ith car.
Return the number of integer points on the line that are covered with any part of a car.
Example 1:
Input: nums = [[3,6],[1,5],[4,7]] Output: 7 Explanation: All the points from 1 to 7 intersect at least one car, therefore the answer would be 7.
Example 2:
Input: nums = [[1,3],[5,8]] Output: 7 Explanation: Points intersecting at least one car are 1, 2, 3, 5, 6, 7, 8. There are a total of 7 points, therefore the answer would be 7.
Constraints:
1 <= nums.length <= 100nums[i].length == 21 <= starti <= endi <= 100Problem Overview: You are given several car parking intervals where each car occupies all integer points between start and end. The task is to count how many distinct integer points are covered by at least one interval.
Approach 1: Brute Force - Use a Set (O(n * range) time, O(range) space)
The simplest way is to simulate all covered points. Iterate through every interval and insert each integer point between start and end into a set. A set automatically removes duplicates, so overlapping segments are handled naturally. After processing all intervals, the answer is simply the size of the set. This approach relies on basic Array traversal and constant-time Hash Table insert operations.
The key idea is that every point is explicitly recorded. If two intervals overlap, the set stores the point only once. This solution is easy to reason about and works well because the coordinate range in the problem is small. Time complexity is proportional to the total number of integer points iterated across all intervals.
Approach 2: Sweep Line Algorithm (Prefix Sum) (O(n + range) time, O(range) space)
A more algorithmic solution uses the sweep line technique with a difference array. Instead of marking every point in every interval, mark where intervals start and end. For each interval [l, r], increment diff[l] and decrement diff[r + 1]. After processing all intervals, run a prefix sum across the array to determine how many active intervals cover each point.
Whenever the running prefix sum is greater than zero, that coordinate is covered by at least one car. Count those positions to get the result. This approach uses the classic Prefix Sum pattern often used in range update problems. Instead of iterating each interval fully, you only process boundaries and reconstruct coverage with one linear pass.
Recommended for interviews: Start with the set-based simulation to show you understand the problem and how overlaps work. Then move to the sweep line / prefix sum method. Interviewers usually prefer this approach because it demonstrates knowledge of range updates and efficient interval processing.
This approach involves iterating over each car's range and adding all integer points to a set data structure, which automatically handles duplicate entries. By the end, the size of the set will represent the count of unique points covered by all cars.
This Python function employs a set to keep track of unique points covered by cars. It iterates through each range in the input list nums, adding each point within the range to the set. Finally, the size of the set is returned as the result.
Time Complexity: O(n * m), where n is the number of cars and m is the average range length of each car.
Space Complexity: O(m), where m is the number of unique points covered.
The sweep line technique is an efficient method for dealing with multiple overlapping intervals. This involves marking the start and end of each car's range on a line, processing these events to calculate coverage, and adjusting the count during overlaps.
In Python, the sweep line algorithm uses event processing to count ranges efficiently. Start and end points of cars trigger events. The sequence of events allows tracking of any active coverage, adding to the total count when applicable.
Python
Java
C++
C#
JavaScript
Time Complexity: O(n log n), due to sorting the event list.
Space Complexity: O(n), for storing the event points.
| Approach | Complexity |
|---|---|
| Brute Force Approach - Use a Set | Time Complexity: O(n * m), where n is the number of cars and m is the average range length of each car. |
| Sweep Line Algorithm | Time Complexity: O(n log n), due to sorting the event list. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force - Set Simulation | O(n * range) | O(range) | Best for small coordinate ranges and quick implementation during interviews |
| Sweep Line (Difference Array + Prefix Sum) | O(n + range) | O(range) | Preferred when processing many intervals efficiently without iterating each point |
LeetCode#2848 Points That Intersect With Cars - Python • CodeJulian • 1,874 views views
Watch 9 more video solutions →Practice Points That Intersect With Cars with our built-in code editor and test cases.
Practice on FleetCode