# Points That Intersect With Cars
**Difficulty:** EASY
[External](https://leetcode.com/problems/points-that-intersect-with-cars)
Canonical: https://scaleengineer.com/dsa/problems/points-that-intersect-with-cars
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
---
## Problem
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 <= 100`
* `nums[i].length == 2`
* `1 <= starti <= endi <= 100`

# Approaches
## Brute Force using HashSet
This is a straightforward brute-force approach. We can use a `HashSet` data structure to keep track of all the unique integer points that are covered by at least one car. We iterate through each car's interval `[start, end]` and add every integer point from `start` to `end` into the set. Since a `HashSet` only stores unique elements, any point covered by multiple cars will only be added once. The final answer is simply the total number of elements in the set.
**Time:** O(N * C), where `N` is the number of cars and `C` is the maximum length of an interval. In the worst case, we iterate through `N` cars, and for each car, we might iterate up to `C` points. Given the constraints `N <= 100` and `C <= 100`, this is feasible. · **Space:** O(C), where `C` is the maximum possible coordinate value (100 in this case). The `HashSet` can store at most all points from 1 to 100. Since `C` is a constant based on the problem constraints, this can be considered O(1) constant space.
**Pros:** The logic is very simple and directly follows the problem description.; It is easy to implement and understand.
**Cons:** This approach can be inefficient if the range of coordinates is very large, as it iterates through every single point within each interval.; It re-processes points multiple times if they are covered by overlapping intervals, although the `HashSet` prevents them from being counted more than once.
### Explanation
The algorithm proceeds as follows:

1.  We initialize a `HashSet` of integers, let's call it `coveredPoints`, which will store all the unique points covered by cars.
2.  We then loop through each car interval provided in the `nums` array.
3.  For each interval `[start, end]`, we use a nested loop to iterate through all integer points from `start` to `end`, inclusive.
4.  Each of these points is added to our `coveredPoints` set. If a point is already in the set, the `add` operation does nothing.
5.  After processing all the intervals, the number of unique covered points is equal to the size of the `coveredPoints` set, which we return as the result.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int numberOfPoints(int[][] nums) {
        Set<Integer> coveredPoints = new HashSet<>();
        for (int[] car : nums) {
            int start = car[0];
            int end = car[1];
            for (int i = start; i <= end; i++) {
                coveredPoints.add(i);
            }
        }
        return coveredPoints.size();
    }
}
```
### Algorithm
- 1. Initialize an empty `HashSet<Integer>` to store the unique integer points covered by cars.
- 2. Iterate through each car's interval `[start, end]` in the input `nums` array.
- 3. For each interval, start a nested loop from `i = start` to `i = end`.
- 4. In the nested loop, add the integer `i` to the `HashSet`. The set will automatically handle duplicates.
- 5. After iterating through all the cars and their corresponding points, the total number of unique points is the size of the `HashSet`.
- 6. Return the size of the set.

## Using a Boolean Array
Given that the coordinates are constrained to a small range [1, 100], we can optimize the previous approach by replacing the `HashSet` with a simple boolean array. This array acts as a direct-access map where the index represents the point on the number line. This method avoids the computational overhead associated with hashing.
**Time:** O(N * C), where `N` is the number of cars and `C` is the coordinate range. The first phase iterates through all points for all cars, and the second phase iterates through the boolean array once. The total complexity is dominated by the first phase. · **Space:** O(C), where `C` is the maximum coordinate value (100). We use a boolean array of a fixed size. Based on the problem constraints, this is O(1) constant space.
**Pros:** Generally faster in practice than the `HashSet` approach due to direct memory access and better cache locality.; It is still simple to implement and understand.; Uses a fixed amount of space determined by the coordinate range.
**Cons:** This approach is only practical when the range of coordinates is small and known in advance.; It has the same asymptotic time complexity as the HashSet approach and is not suitable for problems with a large coordinate range.
### Explanation
We can use a boolean array, say `isCovered`, of size 102 to accommodate all possible coordinates from 1 to 100 (using 1-based indexing). Initially, all entries in this array are `false`.

We iterate through each car interval `[start, end]`. For each point `i` in this range, we set `isCovered[i]` to `true`. This effectively marks the point as being covered by at least one car.

After iterating through all the car intervals, we perform a final pass over the `isCovered` array (from index 1 to 100) and count the number of `true` values. This count gives us the total number of unique points covered by cars.

```java
class Solution {
    public int numberOfPoints(int[][] nums) {
        boolean[] isCovered = new boolean[102]; // Indices 0-101, we use 1-100
        for (int[] car : nums) {
            int start = car[0];
            int end = car[1];
            for (int i = start; i <= end; i++) {
                isCovered[i] = true;
            }
        }
        
        int count = 0;
        for (int i = 1; i <= 100; i++) {
            if (isCovered[i]) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- 1. Create a boolean array, `isCovered`, of size 102 (to handle 1-based indexing up to 100), and initialize all its elements to `false`.
- 2. Iterate through each car interval `[start, end]` in the `nums` array.
- 3. For each interval, loop from `point = start` to `point = end`.
- 4. Inside this loop, mark the point as covered by setting `isCovered[point] = true`.
- 5. After processing all intervals, initialize a counter `count` to 0.
- 6. Iterate through the `isCovered` array from index 1 to 100.
- 7. If `isCovered[i]` is `true`, increment the `count`.
- 8. Return the final `count`.

## Sorting and Merging Intervals
A more scalable and algorithmically efficient approach for interval-based problems is to merge any overlapping intervals. By doing so, we obtain a set of disjoint intervals. The total number of unique points is then the sum of the lengths of these merged, non-overlapping intervals. This method avoids iterating over every single point and is much faster when the coordinate ranges are large.
**Time:** O(N log N), where `N` is the number of cars. The dominant operation is sorting the intervals. The subsequent merging process takes a single pass through the sorted intervals, which is O(N). · **Space:** O(N) in the worst case. The space complexity of the sorting algorithm in Java for an array of objects is O(N). Additionally, the `mergedIntervals` list can store up to `N` intervals if none of them overlap.
**Pros:** This is the most efficient approach with a time complexity of `O(N log N)`.; It is a general solution that works well even if the coordinate range is very large.
**Cons:** The implementation is more complex than the brute-force approaches.; The sorting step adds an `O(N log N)` time cost, which might be slightly slower than `O(N*C)` only if `N` is very large and `C` is very small, which is not the case here.
### Explanation
The key idea is to first sort the intervals based on their starting points. This allows us to process them in an order that makes merging straightforward.

1.  **Sort**: We begin by sorting the `nums` array based on the start point of each interval.
2.  **Merge**: We initialize a list, `mergedIntervals`, to store the result of the merge. We add the first interval from our sorted list to `mergedIntervals`.
3.  We then iterate through the remaining sorted intervals. For each `current` interval, we look at the `last` interval in our `mergedIntervals` list. 
    - If the `current` interval overlaps with the `last` one (i.e., `current[0] <= last[1]`), we merge them by updating the end of the `last` interval to be the maximum of its current end and the `current` interval's end.
    - If there is no overlap, it means we have found a new disjoint interval, so we add the `current` interval to the `mergedIntervals` list.
4.  **Count**: Once we have the final list of disjoint merged intervals, we iterate through this list, calculate the length of each interval (`end - start + 1`), and sum them up to get the total count of covered points.

```java
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public int numberOfPoints(int[][] nums) {
        if (nums.length == 0) return 0;

        Arrays.sort(nums, Comparator.comparingInt(a -> a[0]));

        List<int[]> merged = new ArrayList<>();
        merged.add(nums[0]);

        for (int i = 1; i < nums.length; i++) {
            int[] current = nums[i];
            int[] last = merged.get(merged.size() - 1);

            if (current[0] <= last[1]) { // Overlap
                last[1] = Math.max(last[1], current[1]);
            } else { // No overlap
                merged.add(current);
            }
        }

        int totalPoints = 0;
        for (int[] interval : merged) {
            totalPoints += (interval[1] - interval[0] + 1);
        }

        return totalPoints;
    }
}
```
### Algorithm
- 1. Sort the `nums` array of intervals based on their start points in ascending order.
- 2. If the array is empty, return 0.
- 3. Create a new list, `mergedIntervals`, and add the first interval from the sorted array to it.
- 4. Iterate through the rest of the sorted intervals, from the second one onwards.
- 5. For each `current` interval, compare it with the `last` interval in `mergedIntervals`.
- 6. If the `current` interval overlaps with the `last` one (i.e., `current.start <= last.end`), merge them by updating the end of the `last` interval: `last.end = max(last.end, current.end)`.
- 7. If they do not overlap, add the `current` interval as a new entry to `mergedIntervals`.
- 8. After the merging process is complete, calculate the total number of points by summing the lengths (`end - start + 1`) of all intervals in `mergedIntervals`.

# Solutions
### Java

```java
class Solution {
public
  int numberOfPoints(List<List<Integer>> nums) {
    int[] d = new int[110];
    for (var e : nums) {
      d[e.get(0)]++;
      d[e.get(1) + 1]--;
    }
    int ans = 0, s = 0;
    for (int x : d) {
      s += x;
      if (s > 0) {
        ans++;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfPoints(vector<vector<int>> &nums) {
    int d[110]{};
    for (auto &e : nums) {
      d[e[0]]++;
      d[e[1] + 1]--;
    }
    int ans = 0, s = 0;
    for (int x : d) {
      s += x;
      ans += s > 0;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int: d = [0] * 110 for a, b in nums: d[a] += 1 d[b + 1] -= 1 return sum(s > 0 for s in accumulate(d))

```