algoadvance

Leetcode 2848. Points That Intersect With Cars

Problem Statement

You are given two 1-dimensional arrays cars and points. Each car is represented by its start and end position in cars and each point is represented by its position in points. The task is to count the number of cars that each point intersects.

Example:

Input:
cars = [[1, 5], [3, 7], [6, 9]]
points = [4, 6, 8]

Output:
result = [2, 2, 2]

Explanation:

• Point 4 intersects with cars [1, 5] and [3, 7], so the result for point 4 is 2.
• Point 6 intersects with cars [3, 7] and [6, 9], so the result for point 6 is 2.
• Point 8 intersects with cars [3, 7] and [6, 9], so the result for point 8 is 2.

Clarifying Questions

1. Are the positions of cars and points guaranteed to be in sorted order? No, there is no such guarantee. We should handle unsorted input.

2. Can the car intervals overlap with each other? Yes, the car intervals can overlap.

3. Is it acceptable for the same point to intersect multiple cars? Yes, each point needs to count the number of cars it intersects.

4. Should we consider the start and end of a car as inclusive? Yes, both start and end positions of the cars are inclusive.

Strategy

1. Initialize an array to store the counts for each point.
2. For each point, check how many car intervals it falls into.
3. Iterate over each point and for each point, iterate over all car intervals to check if the point lies within any car interval.
4. Increment the count if the point lies within a car interval.
5. Return the result array containing counts for each point.

Code

Here is the Java code implementing the above strategy:

import java.util.*;

public class PointsIntersectWithCars {
    public static int[] countIntersectingCars(int[][] cars, int[] points) {
        int[] result = new int[points.length];
        
        // Iterate over each point
        for (int i = 0; i < points.length; i++) {
            int point = points[i];
            int count = 0;
            
            // Check this point against every car interval
            for (int[] car : cars) {
                int start = car[0];
                int end = car[1];
                
                if (point >= start && point <= end) {
                    count++;
                }
            }
            
            // Store the result for this point
            result[i] = count;
        }
        
        return result;
    }

    public static void main(String[] args) {
        int[][] cars = { {1, 5}, {3, 7}, {6, 9} };
        int[] points = { 4, 6, 8 };
        
        int[] result = countIntersectingCars(cars, points);
        System.out.println(Arrays.toString(result)); // Output: [2, 2, 2]
    }
}

Time Complexity

The time complexity of this solution is O(n * m) where:

• n is the number of points.
• m is the number of car intervals.

This complexity arises because we have to check each point against every car interval.

Space Complexity

The space complexity is O(n) where n is the number of points, as we store the results in an array of length n.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?