algoadvance

Leetcode 2848. Points That Intersect With Cars

Problem Statement

You are given a 0-indexed 2D integer array cars, where cars[i] = [start_i, end_i] indicates the starting and ending points of the i-th car on an infinite number line.

Return the number of integer points on the line that are covered with exactly one car.

Example

Input: cars = [[1, 3], [2, 5], [6, 8]]
Output: 3

Explanation: The cars cover points 1, 2, 3, 4, 5, 6, 7, 8.
Cars covering each point:
1 -> [1, 3]
2 -> [1, 3], [2, 5]
3 -> [1, 3], [2, 5]
4 -> [2, 5]
5 -> [2, 5]
6 -> [6, 8]
7 -> [6, 8]
8 -> [6, 8]
- Points 1, 4, 6 are covered by exactly one car -> return 3.

Clarifying Questions

  1. What is the range of values for the integer points in start_i and end_i?
    • For simplicity, we will assume they are within a reasonable range that fits within usual integer limits.
  2. How large can the cars array be?
    • Let’s assume we need an efficient solution since the number of intervals can be very large.
  3. Can intervals be overlapping or contiguous?
    • Yes, intervals can overlap and be contiguous, hence we need to count the points that are covered exactly by one car.

Strategy

  1. Use a sweep line technique:
    • This is similar to the line-sweep algorithm where we keep track of how many cars cover each point.
    • We use a map to record the changes in coverage as we hit the start and end+1 of each car’s interval.
  2. Calculate the number of points covered by exactly one car:
    • As we process the map, we keep track of the current coverage.
    • Count the points where the coverage is exactly one.

Time Complexity

Code

#include <vector>
#include <map>

using namespace std;

int countPoints(vector<vector<int>>& cars) {
    map<int, int> events;

    // Record start and end+1 of each interval in the map
    for (auto& car : cars) {
        int start = car[0];
        int end = car[1] + 1;

        events[start]++;
        events[end]--;
    }

    int current_coverage = 0;
    int prev_point = 0;
    int count = 0;

    // Traverse the events in sorted order
    for (auto& event : events) {
        int point = event.first;
        int change = event.second;

        if (current_coverage == 1) {
            count += point - prev_point;
        }

        current_coverage += change;
        prev_point = point;
    }

    return count;
}

int main() {
    vector<vector<int>> cars = \{\{1, 3}, {2, 5}, {6, 8}};
    int result = countPoints(cars);
    // Output: 3 (points 1, 4, 6 are covered by exactly one car)
    printf("%d", result);
    return 0;
}

In the above code:

  1. We used a map to record events (start and end of each car’s interval).
  2. We iterated through the sorted events to count points covered by exactly one car.
  3. For each point where current coverage is exactly one between two consecutive event points, the distance is added to the count.

This method ensures efficient handling of a potentially large input size with intervals.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI