Points That Intersect With Cars

LeetCode 2848: Points That Intersect With Cars (Difference Array Technique)

The problem asks for the total number of unique integer points covered by a set of car intervals $[start,end]$. This solution efficiently tackles the problem using the Difference Array technique.

💻 Code

from typing import List
 
class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        max_coord = 0
        for start, end in nums:
            if end > max_coord:
                max_coord = end
 
        line = [0] * (max_coord + 2)
 
        for start, end in nums:
            line[start] += 1
            line[end + 1] -= 1
 
        ans = 0
        count = 0
        for i in range(1, max_coord + 2):
            count += line[i]
            if count > 0:
                ans += 1
 
        return ans

---

🧠 Code Explanation

The code implements a solution for the LeetCode problem 2848. Points That Intersect With Cars, which aims to find the total count of unique integer points on the number line covered by at least one car interval $[start,end]$. The core of the solution lies in the Difference Array technique, a tool for efficient range updates.

1. Determining the Maximum Coordinate

max_coord = 0
for start, end in nums:
    if end > max_coord:
        max_coord = end
 
line = [0] * (max_coord + 2)

• Purpose: We first iterate through the list of car intervals (nums) to find the largest endpoint (max_coord). This sets the necessary size for our working array, ensuring it can cover all coordinates involved.
• Initialization: The array line (our Difference Array) is initialized with zeros and sized as $\text{max\_coord}+2$. The extra space is needed to safely handle the $\text{end}+1$ index.

---

2. Applying the Difference Array

for start, end in nums:
    line[start] += 1
    line[end + 1] -= 1

• Concept: Instead of marking every point in the interval $[start,end]$, we perform two single-point updates. This transforms an $\mathcal{O}(N)$ range operation into an $\mathcal{O}(1)$ operation.
• Start Point: line[start] += 1 marks the beginning of a car’s coverage. When we calculate the prefix sum, this $+1$ will “turn on” the count from coordinate start onwards.
• End Point: line[end + 1] -= 1 marks the point immediately after the coverage ends. This $-1$ will “turn off” the count, ensuring that only points up to end are considered covered by this car.

💡 Example of Difference Array Update

Car Interval	Action 1: Start	Action 2: End + 1
[3, 5]	line[3] += 1	line[6] -= 1
[1, 4]	line[1] += 1	line[5] -= 1

Assuming $\text{max\_coord}=5$, the line array (indices 1 to 6) would look like this after the updates:

Index $i$	1	2	3	4	5	6
line[i]	+1	0	+1	0	-1	-1

---

3. Calculating the Final Count

ans = 0
count = 0
for i in range(1, max_coord + 2):
    count += line[i]
    if count > 0:
        ans += 1
 
return ans

• Prefix Sum (Sweep Line): This final loop iterates from index 1 and calculates the prefix sum of the line array, storing it in count. The prefix sum is a form of the Sweep Line technique.
• Interpretation: The value of count at any index $i$ represents the net number of cars covering the point $i$.
  • If a start point ($+1$) is encountered, count increases.
  • If an end-plus-one point ($-1$) is encountered, count decreases.
• Counting: If count > 0 at index $i$, it means point $i$ is covered by at least one car. For every such index, we increment the final answer, ans.

💡 Example of Prefix Sum Calculation

Continuing the previous example (intervals [3, 5] and [1, 4]):

Index $i$	line[i]	$\text{count}=\text{count}+\text{line}[i]$	$\text{count}>0$	$\text{ans}$
1	+1	$0+1=1$	True	1
2	0	$1+0=1$	True	2
3	+1	$1+1=2$	True	3
4	0	$2+0=2$	True	4
5	-1	$2+(-1)=1$	True	5
6	-1	$1+(-1)=0$	False	5

The total number of unique covered points is 5 (points 1, 2, 3, 4, and 5).

---

📈 Time Complexity

The time complexity is dominated by the initial pass to find $\text{max\_coord}$ and the final pass to calculate the prefix sum.

• Complexity: $\mathcal{O}(C+M)$, where $C$ is the number of cars and $M$ is $\text{max\_coord}$. This is very efficient for coordinate-based range problems where the coordinates are not astronomically large.