Points That Intersect With Cars
Problem Description
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] = [start i, end i] where start i is the starting point of the ith car and end i 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
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.
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 <= start i <= end i <= 100
The solution for the problem statement can be thought of as checking the length of each car in the nums list one by one and simply checking which all points are covered by the car. Confused about the implementations, let's figure it out together !!
Brute Force Approach
Intuition
Imagine you have a long piece of paper with numbers 1 to 100 written on it, like a number line. Now, think of cars as stickers that can cover parts of this number line. Each car sticker has a starting point and an ending point, like from 3 to 6 or from 1 to 5.
Your job is to find out how many numbers on the paper get covered by any car sticker.
What we do is, we take a new piece of paper and write down the numbers 1 to 100. At the start, all the numbers are "uncovered." .
For each car (sticker), we colour in the numbers from the start to the end of the car.
For example, if a car covers from 3 to 6, we colour 3, 4, 5, and 6. If another car covers from 1 to 5, we colour 1, 2, 3, 4, and 5.
We keep doing this for every car. If a number is already coloured, that's okay! We just leave it coloured.
Finally, we count how many numbers got coloured. That’s the answer!
In the end, you know how many numbers got stickers on them, no matter how many cars (stickers) overlap.
Approach
Initialize a Tracker:
- Create a list or array to track points.
- Set all points as unmarked initially.
Mark Points for Each Range:
- For each range in the list of ranges:
- Extract the start and end of the range.
- Mark all points from start to end as occupied.
Count Marked Points:
- Initialize a counter to zero.
- For each point in the tracker:
- If the point is marked, increment the counter.
Return the Result: Return the answer.
Dry-Run
Initialize a Tracker:
- Create an array tracker of size 101.
- All points are set to false (unmarked).
- Initial State: [F, F, F, F, F, F, F, F, F, F, ...]
Mark Points for Each Range:
Range 1: (2, 5)
- Mark points 2 to 5 as true.
- Tracker Update:
[F, F, T, T, T, T, F, F, F, F, ...]
Range 2: (6, 9)
- Mark points 6 to 9 as true.
- Tracker Update:
[F, F, T, T, T, T, T, T, T, T, ...]
Range 3: (4, 7)
- Mark points 4 to 7 as true (overlaps with previous marks).
- Tracker Update:
[F, F, T, T, T, T, T, T, T, T, ...]
Count Marked Points:
- Traverse the array and count all true (marked) points.
- Points marked: 2, 3, 4, 5, 6, 7, 8, 9
- Total Count: 8
Return the Counter: Output: 8
Brute Force in all Languages
1. C++ Try on Compiler
class Solution {
public:
int numberOfPoints(vector<vector<int>>& nums) {
// Create a boolean array to track parked cars at each point (0-100).
bool parked[101] = {false};
// Iterate over each car's start and end points.
for (auto& info : nums) {
// Get the start and end points of the current car.
int start = info[0];
int end = info[1];
// Mark each point between start and end as true (car parked).
for (int i = start; i <= end; i++) {
parked[i] = true;
}
}
// Initialize the counter for points with parked cars.
int ans = 0;
// Count how many points have parked cars.
for (int i = 0; i < 101; i++) {
if (parked[i]) {
ans++;
}
}
// Return the total number of points with at least one car parked.
return ans;
}
};2. Java Try on Compiler
class Solution {
public int numberOfPoints(List<List<Integer>> nums) {
// Create a boolean array to track parked cars at each point (0-100).
boolean parked[] = new boolean[101];
// Iterate over each car's start and end points.
for (List<Integer> info : nums) {
// Get the start point of the current car.
int start = info.get(0);
// Get the end point of the current car.
int end = info.get(1);
// Mark each point between start and end as true (car parked).
for (int i = start; i <= end; i++) {
parked[i] = true;
}
}
// Initialize the counter for points with parked cars.
int ans = 0;
// Count how many points have parked cars.
for (int i = 0; i < 101; i++) {
if (parked[i]) {
ans++;
}
}
// Return the total number of points with at least one car parked.
return ans;
}
}
3. Python Try on Compiler
class Solution:
def numberOfPoints(self, nums: List[List[int]]) -> int:
# Create a boolean array to track parked cars at each point (0-100).
parked = [False] * 101
# Iterate over each car's start and end points.
for info in nums:
# Get the start and end points of the current car.
start, end = info
# Mark each point between start and end as true (car parked).
for i in range(start, end + 1):
parked[i] = True
# Count how many points have parked cars.
ans = sum(parked)
# Return the total number of points with at least one car parked.
return ans4. JavaScript Try on Compiler
var numberOfPoints = function(nums) {
// Create a boolean array to track parked cars at each point (0-100).
let parked = new Array(101).fill(false);
// Iterate over each car's start and end points.
for (let info of nums) {
// Get the start and end points of the current car.
let start = info[0];
let end = info[1];
// Mark each point between start and end as true (car parked).
for (let i = start; i <= end; i++) {
parked[i] = true;
}
}
// Count how many points have parked cars.
let ans = 0;
for (let i = 0; i < 101; i++) {
if (parked[i]) {
ans++;
}
}
// Return the total number of points with at least one car parked.
return ans;
};Time Complexity: O(n^2)
Outer Loop: Iterates over each range in nums. If there are n ranges, this loop runs n times.
Inner Loop:
- For each range (start, end), the inner loop iterates from start to end.
- In the worst case, this loop can run up to 100 times (if start = 0 and end = 100).
- This gives a time complexity of: O(n⋅k) i.e. O(n^2) Where k is the average size of each range (end - start + 1). In the worst case, k = 101.
Counting Loop: A single pass over the parked array of size 101 takes constant time: O(n)=O(n)
The overall Time Complexity is: O(n^2)
Space Complexity: O(n)
Auxiliary Space Complexity: refers to the additional or extra space used by an algorithm, excluding the space required to store the input data.
parked[] array: A boolean array of size 101 is used: O(101)=O(n) in worst case.
Hence, Auxiliary space complexity is: O(n).
Total Space Complexity (Input + Auxiliary Space):
Input List nums:
- The input list contains n ranges.
- Each range is a list of size 2, contributing O(2n) = O(n).
Auxiliary Space (parked[]): O(n)
Total Space Complexity: O(n)+O(n)= O(2n)= O(n)
Did we observe that even though the cars (stickers) overlap, we were still visiting the previously coloured part and then proceeding further in the approach? Can we utilise this extra runtime and achieve a good time complexity.
Optimal Approach
Intuition
You have a long number line from 1 to 100, just like before. Cars Park on this number line, and each car covers a section of the line.
But instead of colouring every point one by one (which takes time), we use a smart trick to make things faster!
Every time a car begins at a point, we place a little “+1” sign at that starting point.
When the car ends, we place a “-1” sign just after the car's endpoint.
For example: If a car covers from 3 to 6, we put: +1 at 3 (start), -1 at 7 (right after 6, the stop points)
This tells us: From point 3 onward, start counting cars. At point 7, stop counting that car.
Once, we are done with this for all the cars, we will proceed with the final step i.e counting the cars. How?? We will maintain an array parked[] to mark the starting and ending of the cars.
For example: If a car covers from 3 to 6, we put: +1 at parked[3] (start), -1 at parked[7] (right after 6, the stop points)
If another car covers from 4 to 5, we put +1 at parked[4](Start) , -1 at parked[6].
Now, we walk along the number line from left to right: Imagine you are sweeping across the number line from left to right. As you pass each point, you keep track of how many cars are currently covering that point. When a car starts (at the start point), the coverage increases by 1. When a car ends (at endpoint + 1), the coverage decreases by 1.
What we will do is maintain a runningSum and iterate over the parked[] , whenever we encounter a +1, we will add it up to the runningSum signifying that this particular point is covered by a car and a variable "point" signifying that particular area is
So, starting at first we will encounter parked[3] with value +1, so runningSum=1,
next, we encounter parked[4] with value +1, so runningSum=1+1=2.
Next, we encounter parked[5] with value -1, so runningSum= 2-1=1 which means that there is still one car covering this point.
and so on...
This is like placing flags (start and stop signs) along the number line, and as you walk, you adjust how many cars are active at that moment.
We don’t have to colour every point like before. We only need to mark the start and stop for each car – two quick flags for each car and then, we just walk through the number line once to count everything.
The strategy we followed just now is that, as we traversed from left to right, we added up the total number of cars covering each point. If we see a point with active cars (more than zero), we count that point as covered.
The ongoing total count was accumulated using the previous count , are u getting the same intuition as mine?
Yes, it's prefix-sum approach since we carry forward the previous occurrences of cars to the next.
What else ??
Did you observe that we placed two flags i.e. +1 at start and -1 at end which meant that the region between start and end is occupied by the car, as soon as we reached -1, that means the particular space gets un-occupied?
Yes, it's the line sweep algorithm that we unknowingly followed.
What is Line Sweep Algorithm ?
The Line Sweep Algorithm is a computational technique used to process intervals or events that occur over a continuous timeline or 2D space. It involves "sweeping" a vertical or horizontal line across the timeline or space, processing events in a specific order (usually sorted by time or position).
How it works ?
Identify Key Events: Each interval contributes two key events: a start (when the interval begins) and an end (when the interval ends). These events are marked with specific values (e.g., +1 for a start and -1 for an end).
Sweep Through Events
A line sweeps through the events, processing them sequentially. As the sweep progresses, a running total is updated based on the events.
During the sweep, you can calculate or track metrics such as the maximum overlap, total coverage, or active intervals.
Example Dry-Run:
You are given a list of intervals [(1,3),(2,5),(4,6)]. Count the maximum number of overlapping intervals at any point.
Dry Run:
Define Events:For each interval (start,end), create two events:
- (start,+1): An interval starts.
- (end,−1): An interval ends.
Events: [(1,+1),(3,−1),(2,+1),(5,−1),(4,+1),(6,−1)]
Sort Events:
- Sort by time. If times are equal, process ending events first (to handle overlapping properly).
- Sorted Events: [(1,+1),(2,+1),(3,−1),(4,+1),(5,−1),(6,−1)]
Process Events:
- Use a counter to track active intervals.
- Update the counter at each event and track the maximum.
Dry Run: Start with active = 0, max_overlap = 0.
Process events:
1. Event (1,+1): active = 1, max_overlap = 1.
2.Event (2,+1): active = 2, max_overlap = 2.
3.Event (3,−1): active = 1, max_overlap = 2.
4.Event (4,+1): active = 2, max_overlap = 2.
5.Event (5,−1): active = 1, max_overlap = 2.
6.Event (6,−1): active = 0, max_overlap = 2.
Result: The maximum overlap is 2.
Advantages of this algorithm
It is Efficient as it reduces the need for nested iterations or brute force, typically achieving a linear time complexity, where n is the number of events.
It works well in large data-sets.
Quick summary
- Place start (+1) and stop (-1) signs for each car.
- Walk through the line, counting how many cars are covering each point.
- Count the points where at least one car is parked.
Approach
Create a List to Track Points
- Prepare a list that represents points on the number line from 1 to 100.
- Initialize all points to 0 (unmarked).
Mark Start and Stop for Each Car: For each car:
- Add +1 at the car’s starting point (indicating the start of coverage).
- Add -1 at the point just after the car’s end (indicating the end of coverage).
Sweep Across the Line to Track Coverage
- Start at the beginning of the list and move from left to right.
- Keep a running total that tracks how many cars are currently covering each point.
- If the running total is greater than 0 at any point, count that point as covered.
Return the Count of Covered Points: At the end, return the total number of points that are covered by at least one car.
Dry-Run
cars = [[2, 5], [3, 7], [10, 12]]
Initial Setup: n = 101 ; parked array: Initialized with zeros, size 102 (from 0 to 101).
Step 1: Processing Cars Intervals:
- First Car [2, 5]:
- parked[2]++ → parked[2] = 1
- parked[6]-- → parked[6] = -1
- Second Car [3, 7]:
- parked[3]++ → parked[3] = 1
- parked[8]-- → parked[8] = -1
- Third Car [10, 12]:
- parked[10]++ → parked[10] = 1
- parked[13]-- → parked[13] = -1
After Processing Cars: parked = [0, 0, 1, 1, 0, 0, -1, 0, -1, 0, 1, 0, 0, -1, 0, ..., 0]
Step 2: Calculating Points:
- Initialize car = 0 and points = 0
Loop from i = 1 to n
1 → car = 0 → points = 0
i = 2 → car = car + parked[2] = 1 → points++ (points = 1)
i = 3 → car = car + parked[3] = 2 → points++ (points = 2)
i = 4 → car = car + parked[4] = 2 → points++ (points = 3)
i = 5 → car = car + parked[5] = 2 → points++ (points = 4)
i = 6 → car = car + parked[6] = 1 → points++ (points = 5)
i = 7 → car = car + parked[7] = 1 → points++ (points = 6)
i = 8 → car = car + parked[8] = 0 → no increment
i = 9 → car = car + parked[9] = 0 → no increment
i = 10 → car = car + parked[10] = 1 → points++ (points = 7)
i = 11 → car = car + parked[11] = 1 → points++ (points = 8)
i = 12 → car = car + parked[12] = 1 → points++ (points = 9)
i = 13 → car = car + parked[13] = 0 → no increment
Final Points: points = 9
Optimal Code in all Languages
1. C++ Try on Compiler
class Solution {
public:
int numberOfPoints(vector<vector<int>>& cars) {
// Initialize the array to track parked cars at each point.
int n = 101;
vector<int> parked(n + 1, 0);
// Iterate through each car's start and end point to mark the parking.
for (auto& car : cars) {
parked[car[0]]++;
parked[car[1] + 1]--;
}
// Variable to track the number of cars parked at each point.
int car = 0;
int points = 0;
// Traverse through the array to count points where at least one car is parked.
for (int i = 1; i < n; i++) {
car += parked[i];
if (car > 0) {
points++;
}
}
// Return the number of points with at least one car parked.
return points;
}
};
2. Java Try on Compiler
import java.util.*;
class Solution {
public int numberOfPoints(List<List<Integer>> cars) {
// Initialize the array to track parked cars at each point.
int n = 101;
int[] parked = new int[n + 1];
// Iterate through each car's start and end point to mark the parking.
for (List<Integer> car : cars) {
parked[car.get(0)]++;
parked[car.get(1) + 1]--;
}
// Variable to track the number of cars parked at each point.
int car = 0;
int points = 0;
// Traverse through the array to count points where at least one car is parked.
for (int i = 1; i < n; i++) {
car += parked[i];
if (car > 0) {
points++;
}
}
// Return the number of points with at least one car parked.
return points;
}
}3. Python Try on Compiler
class Solution:
def numberOfPoints(self, cars):
# Initialize the array to track parked cars at each point.
n = 101
parked = [0] * (n + 1)
# Iterate through each car's start and end point to mark the parking.
for car in cars:
parked[car[0]] += 1
parked[car[1] + 1] -= 1
# Variable to track the number of cars parked at each point.
car = 0
points = 0
# Traverse through the array to count points where at least one car is parked.
for i in range(1, n):
car += parked[i]
if car > 0:
points += 1
# Return the number of points with at least one car parked.
return points4. JavaScript Try on Compiler
var numberOfPoints = function(cars) {
// Initialize the array to track parked cars at each point.
let n = 101;
let parked = new Array(n + 1).fill(0);
// Iterate through each car's start and end point to mark the parking.
for (let car of cars) {
parked[car[0]]++;
parked[car[1] + 1]--;
}
// Variable to track the number of cars parked at each point.
let car = 0;
let points = 0;
// Traverse through the array to count points where at least one car is parked.
for (let i = 1; i < n; i++) {
car += parked[i];
if (car > 0) {
points++;
}
}
// Return the number of points with at least one car parked.
return points;
};Time Complexity: O(n)
First Loop (Updating the parked array): ➝ This loop iterates over all cars, so its complexity is O(n).
Second Loop (Calculating points): ➝ This loop runs from 1 to 100, hence it iterates O(100) = O(n) times.
Total Time Complexity: O(n)
Space Complexity: O(n)
Auxiliary Space Complexity refers to the extra temporary space or memory used by an algorithm, excluding the input size. It measures the additional space required to perform computations during execution.
- The primary extra space used is the parked array: O(101)=O(n). This is constant space, regardless of the input size.
Total Space Complexity (Including Input Space):
- cars list: If the input list cars contains n cars, each car has two integers. Hence, the total space for the input is: O(2n)=O(n)
- parked array: This contributes an additional O(n) space.
Total Space Complexity: O(n) + O(n)= O(2n)= O(n)
Learning Tip
Given an array of intervals where intervals[i] = [start i, end i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
You are given a 2D integer array logs where each
logs[i] = [birth i, death i] indicates the birth and death years of the ith person.
The population of some year x is the number of people alive during that year. The ith person is counted in year x's population if x is in the inclusive range [birth i, death i- 1]. Note that the person is not counted in the year that they die.
Return the earliest year with the maximum population.