Skip to main content
Talentd

Points That Intersect With Cars - Solution & Explanation

EasyArrayHash TablePrefix Sum18 min readAsked at: Uber
Practice this problem

Problem Statement

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

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.

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.

Code

PythonJavaC++C#JavaScriptC

Python

Java

C++

C#

JavaScript

C

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonJavaC++C#JavaScript

Python

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to sorting the event list.
Space Complexity: O(n), for storing the event points.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(m), where m is the number of unique points covered.

Sweep Line Algorithm

Time Complexity: O(n log n), due to sorting the event list.
Space Complexity: O(n), for storing the event points.

Difference Array—
Hash Table + Difference Array + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force - Set SimulationO(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

Video Solution

Leetcode Weekly contest 362 - Easy - Points That Intersect With Cars - Optmized • Prakhar Agrawal • 1,650 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Points That Intersect With Cars with our built-in code editor and test cases.

Practice on FleetCode
Previous

Meeting Rooms

Next

Meeting Rooms II