Points That Intersect With Cars — Problem & Solution
Points That Intersect With Cars solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Points That Intersect With Cars is an easy coding problem on arrays and prefix sum, asked in Amazon and TCS interviews.
- Difficulty: Easy
- Topics: Arrays, Prefix Sum
- Asked at: Amazon, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a 2D array nums where nums[i] = [start, end] means the i-th car is parked on the integer points from start to end, inclusive.
Return the number of integer points covered by any part of a car.
Example 1
Input: nums = [[3,6],[1,5],[4,7]]
Output: 7
Explanation: Points 1 through 7 are all covered.
Example 2
Input: nums = [[1,3],[5,8]]
Output: 7
Explanation: Points 1,2,3 and 5,6,7,8.
Example 3
Input: nums = [[2,2]]
Output: 1
Constraints
1 <= nums.length <= 100nums[i].length == 21 <= start <= end <= 100
Hints for Points That Intersect With Cars
Hint 1
Coordinates only go up to 100, so a boolean array over the points is plenty.
Hint 2
Mark every point of every car, then count the marks.
Hint 3
A difference array works too and generalises to much larger coordinates.
How to solve Points That Intersect With Cars
The coordinate space is tiny, so marking covered points directly and counting them is both simplest and fastest here.
Approach
- Create a set (or a 101-slot boolean array) of covered points.
- For each car, mark every point from
starttoendinclusive. - Return the number of distinct marked points.
Why it works
Marking is idempotent, so overlapping cars are naturally deduplicated — which is exactly what "covered by any car" means.
Complexity
- Time —
O(n · L) where L is the coordinate range - Space —
O(L)
Pitfalls
- Summing the interval lengths double-counts overlaps.
- The range is inclusive at both ends, so the loop bound is
<= end. - For a much larger coordinate range, sort-and-merge or a difference array is the right tool.
Reference solution
Python
from typing import List
def numberOfPoints(nums: List[List[int]]) -> int:
covered = set()
for s, e in nums:
for p in range(s, e + 1):
covered.add(p)
return len(covered)Java
public static int numberOfPoints(int[][] nums) {
boolean[] covered = new boolean[102];
for (int[] car : nums) {
for (int p = car[0]; p <= car[1]; p++) covered[p] = true;
}
int count = 0;
for (boolean c : covered) if (c) count++;
return count;
}C++
int numberOfPoints(vector<vector<int>>& nums) {
vector<bool> covered(102, false);
for (auto& car : nums) {
for (int p = car[0]; p <= car[1]; p++) covered[p] = true;
}
int count = 0;
for (int p = 0; p < 102; p++) if (covered[p]) count++;
return count;
}JavaScript
var numberOfPoints = function(nums) {
const covered = new Array(102).fill(false);
for (let i = 0; i < nums.length; i++) {
for (let p = nums[i][0]; p <= nums[i][1]; p++) covered[p] = true;
}
let count = 0;
for (let p = 0; p < covered.length; p++) if (covered[p]) count++;
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Prefix Sum