#2848

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Points That Intersect With Cars

Count covered integer points by merging overlapping car intervals or marking visited positions on the number line.

Problem Statement

You get a 0-indexed array nums where each entry is a car segment on a number line. For each nums[i] = [starti, endi], that car covers every integer point from starti through endi, inclusive.

Return how many distinct integer points are covered by at least one car. In the sample nums = [[3,6],[1,5],[4,7]], the covered points run continuously from 1 through 7, so the answer is 7. In nums = [[1,3],[5,8]], the covered points are 1, 2, 3, 5, 6, 7, and 8, which also gives 7.

Examples

Example 1

Input: nums = [[3,6],[1,5],[4,7]]

Output: 7

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

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 <= 100
nums[i].length == 2
1 <= starti <= endi <= 100

Solution Approach

Direct marking with a hash set or boolean array

Because each start and end value is at most 100, you can scan every interval and mark each covered integer point. A hash set fits the Array plus hash lookup pattern directly, while a fixed boolean array is even simpler here. After processing all cars, count how many positions were marked true. This avoids overlap logic entirely, which makes it the safest Easy-level solution.

Sort and merge overlapping intervals

If you want the interval-based interview route, sort nums by start value, then walk from left to right and merge any range whose start is at most the current merged end. Each time a gap appears, add the finished merged segment length as end - start + 1 and start a new segment. This matches the hint about sorting and removing overlap, and it prevents counting the same covered points twice.

Prefix sum over the number line

Since coordinates are small, you can also use a difference array. Add 1 at starti and subtract 1 at endi + 1, then build a prefix sum across the line. Every index with running sum greater than 0 is covered by at least one car. This connects the problem to Prefix Sum and is useful when you want to count covered points without touching every interval position separately in larger coordinate settings.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The marking solution runs in O(n * L) time, where L is the average interval length, and uses O(U) space for the covered positions, with U at most 100 here. The sort-and-merge solution runs in O(n log n) time for sorting and O(1) or O(n) extra space depending on implementation. The prefix sum method runs in O(n + U) time and O(U) space, which is very efficient in this problem because the coordinate range is tiny.

What Interviewers Usually Probe

The small coordinate bound up to 100 is a strong signal that brute-force marking each integer point is fully acceptable.
If the interviewer mentions overlap removal or sorting by the first element, they are steering toward interval merging.
If they ask for a cleaner counting trick instead of repeated point insertion, they may want the Prefix Sum difference-array version.

Common Pitfalls or Variants

Common pitfalls

Forgetting that intervals are inclusive causes off-by-one errors, especially when computing merged length as end - start + 1.
Double-counting overlap happens when you sum each car length independently instead of merging or deduplicating points.
Using endi + 1 in the prefix method without allocating enough space can break the last update boundary.

Follow-up variants

Return the actual covered points instead of only the count, which favors the marking approach.
Increase coordinate bounds dramatically, which makes sort-and-merge more practical than point-by-point scanning.
Ask how many points are covered by at least k cars, which turns the Prefix Sum running count into the key extension.

FAQ

What is the easiest way to solve Points That Intersect With Cars?

The easiest solution is to mark every integer point covered by each car using a boolean array or hash set, then count the marked positions. It works especially well because all coordinates are between 1 and 100.

Why does interval merging work for this problem?

Merging works because overlapping car ranges cover one continuous block of integer points. After sorting by start, you can combine overlaps and add each merged block length once, which avoids double-counting.

Is prefix sum overkill for this problem?

It is not necessary for the given limits, but it is still a valid and neat approach. It becomes more interesting when you want to count coverage from many intervals or extend the task to coverage frequency.

What is the main failure mode in this pattern?

The main failure mode is double-counting points that belong to multiple overlapping cars. Another common mistake is forgetting that both start and end are included in the covered segment.

How does the array scanning plus hash lookup pattern apply here?

You scan each interval in nums and insert every covered integer point into a set, or mark it in a boolean array. The lookup structure guarantees each point is counted once even when intervals overlap heavily.

terminal

Solution

Solution 1: Difference Array

According to the problem description, we need to add one vehicle to each interval $[\textit{start}_i, \textit{end}_i]$. We can use a difference array to achieve this.

1

2

3

4

5

6

7

8

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        m = 102
        d = [0] * m
        for start, end in nums:
            d[start] += 1
            d[end + 1] -= 1
        return sum(s > 0 for s in accumulate(d))

Solution 2: Hash Table + Difference Array + Sorting

If the range of intervals in the problem is large, we can use a hash table to store the start and end points of the intervals. Then, we sort the keys of the hash table and perform prefix sum statistics.

1

2

3

4

5

6

7

8

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        m = 102
        d = [0] * m
        for start, end in nums:
            d[start] += 1
            d[end + 1] -= 1
        return sum(s > 0 for s in accumulate(d))

Continue Practicing

#2845 count of interesting subarrays #2875 minimum size subarray in infinite array #3026 maximum good subarray sum