Watch 10 video solutions for Points That Intersect With Cars, a easy level problem involving Array, Hash Table, Prefix Sum. This walkthrough by CodeJulian has 1,874 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |