Scale Engineer

Points That Intersect With Cars

Easy
#2547Time: 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.
Patterns
Prefix Sum
Data structures
ArrayHash Table

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Algorithm

    1. Initialize an empty HashSet<Integer> to store the unique integer points covered by cars.
    1. Iterate through each car's interval [start, end] in the input nums array.
    1. For each interval, start a nested loop from i = start to i = end.
    1. In the nested loop, add the integer i to the HashSet. The set will automatically handle duplicates.
    1. After iterating through all the cars and their corresponding points, the total number of unique points is the size of the HashSet.
    1. Return the size of the set.

Walkthrough

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.
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();    }}

Complexity

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.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem