Points That Intersect With Cars solution and explanation
9 more videos on this problem
Leetcode Weekly contest 362 - Easy - Points That Intersect With Cars - OptmizedPrakhar Agrawal · 9:24 · 1K views
2848. Points That Intersect With Cars (Leetcode Easy)Programming Live with Larry · 2:12 · 819 views
Leetcode 2848 Points That Intersect With CarsTech Diet · 4:34 · 768 views
8029. Points That Intersect With Cars LeetCode weekly contest 362 solution #leetcode #contestContest Codes · 0:21 · 602 views
points that intersect with cars #leetcodechallenge #leetcode #contest 362crazy developers · 0:27 · 387 views
Weekly Contest 362 || 2848. Points That Intersect With Cars || Easy Problem and Easy ExplanationManas Kumar Panda · 8:44 · 387 views
2848. Points That Intersect With CarsChill With Gobane · 3:14 · 209 views
Leetcode 2848: Points That Intersect With Cars in Telugu | Python DSA | srkcodesSrk Codes · 7:59 · 113 views
leetcode 2848[Telsa Q]. Points That Intersect With Cars - prototype: interval merge type problemCode-Yao · 7:15 · 98 views
8029. Points That Intersect With Cars || weekly contest 362 answerCygnatrix · 0:59 · 94 views
The 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 <= 100nums[i].length == 21 <= starti <= endi <= 100
Approach overview
Problem Overview: You are given several car parking intervals where each car occupies all integer points between start and end. The task is to count how many distinct integer points are covered by at least one interval.
Approach 1: Brute Force - Use a Set (O(n * range) time, O(range) space)
The simplest way is to simulate all covered points. Iterate through every interval and insert each integer point between start and end into a set. A set automatically removes duplicates, so overlapping segments are handled naturally. After processing all intervals, the answer is simply the size of the set. This approach relies on basic Array traversal and constant-time Hash Table insert operations.
The key idea is that every point is explicitly recorded. If two intervals overlap, the set stores the point only once. This solution is easy to reason about and works well because the coordinate range in the problem is small. Time complexity is proportional to the total number of integer points iterated across all intervals.
Approach 2: Sweep Line Algorithm (Prefix Sum) (O(n + range) time, O(range) space)
A more algorithmic solution uses the sweep line technique with a difference array. Instead of marking every point in every interval, mark where intervals start and end. For each interval [l, r], increment diff[l] and decrement diff[r + 1]. After processing all intervals, run a prefix sum across the array to determine how many active intervals cover each point.
Whenever the running prefix sum is greater than zero, that coordinate is covered by at least one car. Count those positions to get the result. This approach uses the classic Prefix Sum pattern often used in range update problems. Instead of iterating each interval fully, you only process boundaries and reconstruct coverage with one linear pass.
Recommended for interviews: Start with the set-based simulation to show you understand the problem and how overlaps work. Then move to the sweep line / prefix sum method. Interviewers usually prefer this approach because it demonstrates knowledge of range updates and efficient interval processing.
Approach 1: Brute Force Approach - Use a Set
This approach involves iterating over each car's range and adding all integer points to a set data structure, which automatically handles duplicate entries. By the end, the size of the set will represent the count of unique points covered by all cars.
def countCoveredPoints(nums):
points = set()
for start, end in nums:
for point in range(start, end + 1):
points.add(point)
return len(points)
nums = [[3, 6], [1, 5], [4, 7]]
print(countCoveredPoints(nums)) # Output: 7import java.util.HashSet;
import java.util.Set;
public class CountingPoints {
public static int countCoveredPoints(int[][] nums) {
Set<Integer> points = new HashSet<>();
for (int[] range : nums) {
for (int i = range[0]; i <= range[1]; i++) {
points.add(i);
}
}
return points.size();
}
public static void main(String[] args) {
int[][] nums = {{3, 6}, {1, 5}, {4, 7}};
System.out.println(countCoveredPoints(nums)); // Output: 7
}
}#include <iostream>
#include <unordered_set>
#include <vector>
int countCoveredPoints(std::vector<std::vector<int>>& nums) {
std::unordered_set<int> points;
for (const auto& range : nums) {
for (int i = range[0]; i <= range[1]; ++i) {
points.insert(i);
}
}
return points.size();
}
int main() {
std::vector<std::vector<int>> nums = {{3, 6}, {1, 5}, {4, 7}};
std::cout << countCoveredPoints(nums) << std::endl; // Output: 7
return 0;
}function countCoveredPoints(nums) {
const points = new Set();
nums.forEach(range => {
for (let i = range[0]; i <= range[1]; i++) {
points.add(i);
}
});
return points.size;
}
const nums = [[3, 6], [1, 5], [4, 7]];
console.log(countCoveredPoints(nums)); // Output: 7#include <stdio.h>
#include <stdbool.h>
#define MAX_POINTS 101
int countCoveredPoints(int nums[][2], int numsSize) {
bool points[MAX_POINTS] = {false};
int count = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = nums[i][0]; j <= nums[i][1]; j++) {
if (!points[j]) {
points[j] = true;
count++;
}
}
}
return count;
}
int main() {
int nums[3][2] = {{3, 6}, {1, 5}, {4, 7}};
printf("%d\n", countCoveredPoints(nums, 3)); // Output: 7
return 0;
}using System;
using System.Collections.Generic;
class CountingPoints {
static int CountCoveredPoints(int[][] nums) {
HashSet<int> points = new HashSet<int>();
foreach (var range in nums) {
for (int i = range[0]; i <= range[1]; i++) {
points.Add(i);
}
}
return points.Count;
}
static void Main() {
int[][] nums = { new int[] { 3, 6 }, new int[] { 1, 5 }, new int[] { 4, 7 } };
Console.WriteLine(CountCoveredPoints(nums)); // Output: 7
}
}This Python function employs a set to keep track of unique points covered by cars. It iterates through each range in the input list nums, adding each point within the range to the set. Finally, the size of the set is returned as the result.
Time Complexity: O(n * m), where n is the number of cars and m is the average range length of each car.
Space Complexity: O(m), where m is the number of unique points covered.
Approach 2: Sweep Line Algorithm
The sweep line technique is an efficient method for dealing with multiple overlapping intervals. This involves marking the start and end of each car's range on a line, processing these events to calculate coverage, and adjusting the count during overlaps.
def countCoveredPoints(nums):
events = []
for start, end in nums:
events.append((start, 1)) # start of a car
events.append((end + 1, -1)) # end of a car
events.sort() # sort events by position
current_active = 0
last_position = None
covered_points = 0
for position, event in events:
if current_active > 0 and last_position is not None:
covered_points += position - last_position
current_active += event
last_position = position
return covered_points
nums = [[3, 6], [1, 5], [4, 7]]
print(countCoveredPoints(nums)) # Output: 7import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SweepLineCounter {
public static int countCoveredPoints(int[][] nums) {
List<int[]> events = new ArrayList<>();
for (int[] range : nums) {
events.add(new int[] {range[0], 1}); // Start of car
events.add(new int[] {range[1] + 1, -1}); // End of car
}
events.sort((a, b) -> a[0] - b[0]);
int currentActive = 0;
Integer lastPosition = null;
int coveredPoints = 0;
for (int[] event : events) {
if (currentActive > 0 && lastPosition != null) {
coveredPoints += event[0] - lastPosition;
}
currentActive += event[1];
lastPosition = event[0];
}
return coveredPoints;
}
public static void main(String[] args) {
int[][] nums = { {3, 6}, {1, 5}, {4, 7} };
System.out.println(countCoveredPoints(nums)); // Output: 7
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int countCoveredPoints(vector<vector<int>>& nums) {
vector<pair<int, int>> events;
for (const auto& range : nums) {
events.emplace_back(range[0], 1); // Car start
events.emplace_back(range[1] + 1, -1); // Car end
}
sort(events.begin(), events.end());
int currentActive = 0;
int lastPosition = -1;
int coveredPoints = 0;
for (const auto& event : events) {
if (currentActive > 0 && lastPosition != -1) {
coveredPoints += event.first - lastPosition;
}
currentActive += event.second;
lastPosition = event.first;
}
return coveredPoints;
}
int main() {
vector<vector<int>> nums = {{3, 6}, {1, 5}, {4, 7}};
cout << countCoveredPoints(nums) << endl; // Output: 7
return 0;
}function countCoveredPoints(nums) {
const events = [];
nums.forEach(range => {
events.push([range[0], 1]); // Car start
events.push([range[1] + 1, -1]); // Car end
});
events.sort((a, b) => a[0] - b[0]);
let currentActive = 0;
let lastPosition = null;
let coveredPoints = 0;
events.forEach(([position, type]) => {
if (currentActive > 0 && lastPosition !== null) {
coveredPoints += position - lastPosition;
}
currentActive += type;
lastPosition = position;
});
return coveredPoints;
}
const nums = [[3, 6], [1, 5], [4, 7]];
console.log(countCoveredPoints(nums)); // Output: 7using System;
using System.Collections.Generic;
class SweepLineCounter {
static int CountCoveredPoints(int[][] nums) {
List<int[]> events = new List<int[]>();
foreach (var range in nums) {
events.Add(new int[] {range[0], 1}); // Start point
events.Add(new int[] {range[1] + 1, -1}); // End point
}
events.Sort((a, b) => a[0].CompareTo(b[0]));
int currentActive = 0, coveredPoints = 0;
int? lastPosition = null;
foreach (var eventPoint in events) {
if (currentActive > 0 && lastPosition != null) {
coveredPoints += eventPoint[0] - (int)lastPosition;
}
currentActive += eventPoint[1];
lastPosition = eventPoint[0];
}
return coveredPoints;
}
static void Main() {
int[][] nums = { new int[] {3, 6}, new int[] {1, 5}, new int[] {4, 7} };
Console.WriteLine(CountCoveredPoints(nums)); // Output: 7
}
}In Python, the sweep line algorithm uses event processing to count ranges efficiently. Start and end points of cars trigger events. The sequence of events allows tracking of any active coverage, adding to the total count when applicable.
Time Complexity: O(n log n), due to sorting the event list.
Space Complexity: O(n), for storing the event points.
Approach 3: Difference Array
According to the problem description, we need to add one vehicle to each interval [start_i, end_i]. We can use a difference array to achieve this.
We define an array d of length 102. For each interval [start_i, end_i], we increment d[start_i] by 1 and decrement d[end_i + 1] by 1.
Finally, we perform a prefix sum operation on d and count the number of elements in the prefix sum that are greater than 0.
The time complexity is O(n + m), and the space complexity is O(m), where n is the length of the given array, and m is the maximum value in the array. In this problem, m leq 102.
function numberOfPoints(nums: number[][]): number {
const d: number[] = Array(102).fill(0);
for (const [start, end] of nums) {
++d[start];
--d[end + 1];
}
let ans = 0;
let s = 0;
for (const x of d) {
s += x;
ans += s > 0 ? 1 : 0;
}
return ans;
}func numberOfPoints(nums [][]int) (ans int) {
d := [102]int{}
for _, e := range nums {
start, end := e[0], e[1]
d[start]++
d[end+1]--
}
s := 0
for _, x := range d {
s += x
if s > 0 {
ans++
}
}
return
}Approach 4: Hash Table + Difference Array + Sorting
If the range of intervals in the problem is large, we can use a hash table to store the start and end points of the intervals. Then, we sort the keys of the hash table and perform prefix sum statistics.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the given array.
function numberOfPoints(nums: number[][]): number {
const d = new Map<number, number>();
for (const [start, end] of nums) {
d.set(start, (d.get(start) || 0) + 1);
d.set(end + 1, (d.get(end + 1) || 0) - 1);
}
const keys = [...d.keys()].sort((a, b) => a - b);
let [ans, s, last] = [0, 0, 0];
for (const cur of keys) {
if (s > 0) {
ans += cur - last;
}
s += d.get(cur)!;
last = cur;
}
return ans;
}func numberOfPoints(nums [][]int) (ans int) {
d := map[int]int{}
for _, e := range nums {
start, end := e[0], e[1]
d[start]++
d[end+1]--
}
keys := []int{}
for k := range d {
keys = append(keys, k)
}
s, last := 0, 0
sort.Ints(keys)
for _, cur := range keys {
if s > 0 {
ans += cur - last
}
s += d[cur]
last = cur
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach - Use a Set | Time Complexity: O(n * m), where n is the number of cars and m is the average range length of each car. |
| Sweep Line Algorithm | Time Complexity: O(n log n), due to sorting the event list. |
| Difference Array | – |
| Hash Table + Difference Array + Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force - Set Simulation | O(n * range) | O(range) | Best for small coordinate ranges and quick implementation during interviews |
| Sweep Line (Difference Array + Prefix Sum) | O(n + range) | O(range) | Preferred when processing many intervals efficiently without iterating each point |
Frequently asked questions
Is Points That Intersect With Cars easy or hard?
LeetCode classifies this problem as Easy. The straightforward set simulation is simple to implement, while the sweep line solution introduces a useful prefix sum technique often used in interval and range update problems.
Points That Intersect With Cars Python/Java solution
Most implementations follow either set simulation or sweep line logic. In Python and Java, iterate through intervals inserting points into a set, or build a difference array and compute prefix sums to count covered positions efficiently.
How to solve Points That Intersect With Cars in O(n)?
Use a sweep line with a difference array. For each interval [l, r], increment diff[l] and decrement diff[r+1]. Compute the prefix sum across the array and count positions where the running value is greater than zero. This processes intervals in O(n) and scans the range once.
What is the best approach for Points That Intersect With Cars?
The sweep line algorithm using a difference array and prefix sum is the best approach. It marks where intervals start and end, then reconstructs coverage with a single prefix sum pass. This runs in O(n + range) time and avoids iterating every point in every interval.
Is Points That Intersect With Cars asked at Google/Amazon/Meta?
Interval coverage and sweep line problems frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying concepts—interval processing, prefix sums, and range counting—are common interview patterns.
What data structure is used in Points That Intersect With Cars?
Two main data structures are used. The brute force approach uses a Hash Set to store unique covered points. The optimized approach uses an array-based difference array combined with prefix sums to efficiently track interval coverage.
What is the time complexity of Points That Intersect With Cars?
The brute force set simulation runs in O(n * range) time because every point inside each interval may be visited. The sweep line prefix sum approach improves this to O(n + range) by processing only interval boundaries and scanning the coordinate range once.