Points That Intersect With Cars

Difficulty: Easy | Acceptance: 73.30% | Paid: No Topics: Array, Hash Table, Prefix Sum

You are given a 0-indexed 2D integer array nums representing the coordinates of cars parked on a number line. For nums[i] = [start_i, end_i], the car i is at the coordinate start_i and moves towards end_i (inclusive).

Return the number of integer points on the number line that are covered by any car.

Examples

Example 1

Input: nums = [[3,6],[1,5],[4,7]]
Output: 7
Explanation: The integer points covered by cars are 1, 2, 3, 4, 5, 6, 7.

Example 2

Input: nums = [[1,3],[5,8]]
Output: 7
Explanation: The integer points covered by cars are 1, 2, 3, 5, 6, 7, 8.

Constraints

1 <= nums.length <= 100
1 <= nums[i].length == 2
1 <= start_i <= end_i <= 100

• Examples
• Constraints
• Approach 1: Boolean Array / Simulation
• Approach 2: Sorting and Merging Intervals
• Approach 3: Prefix Sum / Line Sweep

Examples

Example 1

Input: nums = [[3,6],[1,5],[4,7]]
Output: 7
Explanation: The integer points covered by cars are 1, 2, 3, 4, 5, 6, 7.

Example 2

Input: nums = [[1,3],[5,8]]
Output: 7
Explanation: The integer points covered by cars are 1, 2, 3, 5, 6, 7, 8.

Constraints

1 <= nums.length <= 100
1 <= nums[i].length == 2
1 <= start_i <= end_i <= 100

Boolean Array / Simulation

Intuition Since the coordinate range is strictly limited to 1 through 100, we can simulate the coverage directly using a boolean array (or a hash set) to mark which points are occupied.

Steps

• Initialize a boolean array seen of size 101 (indices 0 to 100) with false.
• Iterate through each car interval [start, end] in nums.
• For each interval, loop from start to end (inclusive) and set seen[i] to true.
• Finally, count the number of true values in the seen array.

class Solution:
    def numberOfPoints(self, nums: list[list[int]]) -> int:
        seen = [False] * 101
        for start, end in nums:
            for i in range(start, end + 1):
                seen[i] = True
        return sum(seen)

Complexity

• Time: O(N * L), where N is the number of cars and L is the average length of the interval. Since L <= 100, this is effectively O(N).
• Space: O(1), as the array size is fixed at 101 regardless of input.
• Notes: This is the most straightforward approach given the small constraint on coordinate values.

Sorting and Merging Intervals

Intuition We can treat the cars as intervals on a number line. By sorting these intervals by their start time, we can merge overlapping or adjacent intervals and simply sum the lengths of the merged intervals.

Steps

• Sort the nums array based on the start coordinate of each interval.
• Initialize result to 0, and variables currStart and currEnd to track the current merged interval.
• Iterate through the sorted intervals:
  • If the current interval starts after currEnd, it means the previous interval has ended. Add its length (currEnd - currStart + 1) to result and start a new interval with the current coordinates.
  • Otherwise, the intervals overlap or touch. Update currEnd to be the maximum of currEnd and the current interval’s end.
• After the loop, add the length of the last tracked interval to result.

class Solution:
    def numberOfPoints(self, nums: list[list[int]]) -> int:
        nums.sort(key=lambda x: x[0])
        res = 0
        curr_start, curr_end = -1, -1
        for s, e in nums:
            if s > curr_end:
                if curr_start != -1:
                    res += curr_end - curr_start + 1
                curr_start, curr_end = s, e
            else:
                curr_end = max(curr_end, e)
        res += curr_end - curr_start + 1
        return res

Complexity

• Time: O(N log N) due to the sorting step, where N is the number of cars.
• Space: O(1) or O(log N) depending on the sorting algorithm’s space complexity.
• Notes: This approach is efficient and generalizes well to larger coordinate ranges where a boolean array would be too large.

Prefix Sum / Line Sweep

Intuition We can use a difference array (or line sweep) technique. We increment a counter at the start of an interval and decrement it just after the end. Calculating the prefix sum of this array tells us how many cars cover each point.

Steps

• Initialize an array diff of size 102 (to safely handle index end + 1 up to 100) with zeros.
• For each interval [start, end] in nums:
  • Increment diff[start] by 1.
  • Decrement diff[end + 1] by 1.
• Compute the prefix sum by iterating from 1 to 100. Maintain a running currentCoverage.
• If currentCoverage is greater than 0, it means the point is covered by at least one car, so increment the result.

class Solution:
    def numberOfPoints(self, nums: list[list[int]]) -> int:
        diff = [0] * 102
        for start, end in nums:
            diff[start] += 1
            diff[end + 1] -= 1
        
        res = 0
        curr = 0
        for i in range(1, 101):
            curr += diff[i]
            if curr > 0:
                res += 1
        return res

Complexity

• Time: O(N + C), where N is the number of cars and C is the maximum coordinate value (100).
• Space: O(C) to store the difference array.
• Notes: This is highly efficient for multiple range queries on a fixed range.