Problem Description

You are given a 2D array nums where each element represents a car parked on a number line. Each car is described by nums[i] = [start_i, end_i], where:

• start_i is the starting position of the i-th car
• end_i is the ending position of the i-th car

A car covers all integer points from its starting position to its ending position (inclusive). For example, a car at [2, 5] covers the integer points 2, 3, 4, and 5.

Your task is to find the total number of unique integer points on the number line that are covered by at least one car. If multiple cars cover the same point, that point should only be counted once.

For example:

• If nums = [[3, 6], [1, 5], [4, 7]], the cars cover points:
  • First car: 3, 4, 5, 6
  • Second car: 1, 2, 3, 4, 5
  • Third car: 4, 5, 6, 7
• The unique points covered are: 1, 2, 3, 4, 5, 6, 7
• The answer would be 7

The solution uses a difference array technique to efficiently track which points are covered by at least one car. By marking the start and end+1 positions of each car's range, and then computing the prefix sum, we can determine which points have at least one car covering them.

Intuition

The key insight is that we need to track which points on the number line are covered by at least one car. A straightforward approach would be to mark each point for every car interval, but this could be inefficient with many overlapping intervals.

Instead, we can think about this problem in terms of "events" happening on the number line. When a car starts at position start, it begins covering points. When a car ends at position end, it stops covering points after that position.

This leads us to the difference array technique. Rather than marking every single point in each interval, we only mark the boundaries:

• When we encounter the start of a car at position start, we know that from this point onwards, one more car is covering the line, so we add +1 at d[start]
• When we pass the end of a car at position end, we know that after end, one fewer car is covering the line, so we add -1 at d[end + 1]

After marking all these boundary events, we can perform a cumulative sum (prefix sum) on the array. At any position i, the cumulative sum tells us how many cars are currently covering that position. If the cumulative sum is greater than 0, it means at least one car covers that point.

For example, with cars at [1,3] and [2,4]:

• We mark +1 at position 1 (first car starts)
• We mark +1 at position 2 (second car starts)
• We mark -1 at position 4 (first car ends after position 3)
• We mark -1 at position 5 (second car ends after position 4)
• The prefix sum gives us: positions 1,2,3,4 have positive values, indicating they are covered

This approach efficiently handles overlapping intervals and gives us the count of covered points in linear time.

Learn more about Prefix Sum patterns.

Solution Approach

The solution implements the difference array technique to efficiently count the covered points:

1. Initialize the Difference Array: Create an array d of size 102 (sufficient to handle the problem constraints). This array will track the changes in coverage at each position.

2. Mark Interval Boundaries: For each car interval [start, end]:

   • Increment d[start] by 1 to indicate a car starts covering from this position
   • Decrement d[end + 1] by 1 to indicate a car stops covering after position end

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

3. Compute Prefix Sum: Use Python's accumulate function to compute the cumulative sum of the difference array. At each position, the cumulative sum represents the number of cars covering that position.

4. Count Covered Points: Count how many positions have a positive cumulative sum value, which indicates at least one car covers that point:

   return sum(s > 0 for s in accumulate(d))

The beauty of this approach is its efficiency:

• Time Complexity: O(n + m) where n is the number of cars and m is the range of positions (102 in this case)
• Space Complexity: O(m) for the difference array

By using the difference array pattern, we avoid the need to iterate through every point in every interval, making the solution much more efficient than a brute force approach that would mark each individual point for each car.

Example Walkthrough

Let's walk through a small example with nums = [[1, 3], [2, 5]] to illustrate the solution approach.

Step 1: Initialize the difference array We create an array d of size 102, initially all zeros. We'll only show positions 0-7 for clarity:

Position: 0  1  2  3  4  5  6  7
d:        0  0  0  0  0  0  0  0

Step 2: Process the first car [1, 3]

• Car starts at position 1, so we add +1 at d[1]
• Car ends at position 3, so we add -1 at d[3+1] = d[4]

Position: 0  1  2  3  4  5  6  7
d:        0  1  0  0 -1  0  0  0

Step 3: Process the second car [2, 5]

• Car starts at position 2, so we add +1 at d[2]
• Car ends at position 5, so we add -1 at d[5+1] = d[6]

Position: 0  1  2  3  4  5  6  7
d:        0  1  1  0 -1  0 -1  0

Step 4: Compute the prefix sum We calculate the cumulative sum of the difference array:

Position:     0  1  2  3  4  5  6  7
d:            0  1  1  0 -1  0 -1  0
Prefix sum:   0  1  2  2  1  1  0  0

The prefix sum at each position tells us:

• Position 0: 0 cars covering (not covered)
• Position 1: 1 car covering (covered by first car)
• Position 2: 2 cars covering (covered by both cars)
• Position 3: 2 cars covering (covered by both cars)
• Position 4: 1 car covering (covered by second car only)
• Position 5: 1 car covering (covered by second car only)
• Position 6: 0 cars covering (not covered)
• Position 7: 0 cars covering (not covered)

Step 5: Count covered points We count positions where the prefix sum is greater than 0:

• Positions 1, 2, 3, 4, 5 have positive values
• Total: 5 unique points are covered

Verification:

• First car [1, 3] covers: {1, 2, 3}
• Second car [2, 5] covers: {2, 3, 4, 5}
• Union of covered points: {1, 2, 3, 4, 5}
• Count: 5 points ✓

This matches our solution! The difference array technique efficiently tracks coverage changes at boundaries, and the prefix sum reveals which points are covered by at least one car.

Solution Implementation

Time and Space Complexity

The time complexity is O(n + m), where n is the number of intervals in the input array nums and m is the fixed size of the difference array (102 in this case). The algorithm iterates through all n intervals once to populate the difference array with O(1) operations per interval, then uses accumulate to compute prefix sums over the m-sized array, resulting in O(n + m) total time.

The space complexity is O(m), where m = 102 is the fixed size of the difference array d. The algorithm allocates an array of size m to track the difference values, and the accumulate function generates values one at a time without creating an additional array, so the dominant space usage is the O(m) difference array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error with Interval End Points

One of the most common mistakes when implementing the difference array technique is incorrectly handling the end boundary of intervals.

The Pitfall: Developers often mistakenly decrement at diff_array[end] instead of diff_array[end + 1]:

# INCORRECT - This would exclude the endpoint from coverage
for start, end in nums:
    diff_array[start] += 1
    diff_array[end] -= 1  # Wrong! This stops coverage before the endpoint

Why This Happens: The confusion arises because intervals are inclusive of both endpoints [start, end], meaning a car at position [3, 5] covers points 3, 4, AND 5. The difference array technique requires us to mark where coverage stops, which is the position after the last covered point.

The Solution: Always decrement at end + 1 to ensure the endpoint itself remains covered:

# CORRECT - Ensures the endpoint is included in coverage
for start, end in nums:
    diff_array[start] += 1
    diff_array[end + 1] -= 1  # Correct! Coverage stops after the endpoint

2. Array Size and Index Out of Bounds

The Pitfall: Using an array that's too small or not accounting for the end + 1 operation can cause index out of bounds errors:

# INCORRECT - May cause IndexError if any end value is 101
diff_array = [0] * 101  # Too small if we have end=101 and access end+1

The Solution: Always allocate sufficient space considering the maximum possible value plus the offset needed for end + 1:

# CORRECT - Accounts for maximum end value plus 1
max_coordinate = 102  # If max end is 101, we need index 102
diff_array = [0] * max_coordinate

3. Misunderstanding the Accumulate Result

The Pitfall: Some developers might forget that accumulate() returns an iterator and try to use it multiple times or incorrectly interpret its values:

# INCORRECT - accumulate returns an iterator that gets exhausted
prefix_sums = accumulate(diff_array)
count1 = sum(s > 0 for s in prefix_sums)  # Works
count2 = sum(s > 0 for s in prefix_sums)  # Returns 0! Iterator exhausted

The Solution: Either convert to a list if you need to reuse the values, or compute directly in one pass:

# CORRECT - Single pass computation
return sum(coverage > 0 for coverage in accumulate(diff_array))

# OR if you need to reuse:
prefix_sums = list(accumulate(diff_array))
return sum(s > 0 for s in prefix_sums)