Car Pooling
Problem Description
There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).
You are given the integer capacity and an array trips where trips[i] = [numPassengers i, from i, to i] indicates that the ith trip has numPassengers i passengers and the locations to pick them up and drop them off are from i and to i respectively. The locations are given as the number of kilometers due east from the car's initial location.
Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.
Examples
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Explanation: Trip 1: 2 passengers are picked up at km 1 and dropped off at km 5. Trip 2: 3 passengers are picked up at km 3 and dropped off at km 7. At km 3 to km 5, both trips overlap, resulting in 2 + 3 = 5 passengers in the car. This exceeds the capacity of 4, so the answer is false.
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
Explanation: Trip 1: 2 passengers at km 1 to km 5. Trip 2: 3 passengers at km 3 to km 7. The maximum number of passengers at any point is 5, which matches the car's capacity. Hence, the answer is true.
Constraints:
- 1 <= trips.length <= 1000
- trips[i].length == 3
- 1 <= numPassengers i <= 100
- 0 <= from i < to i <= 1000
- 1 <= capacity <= 10^5
Is the first intuitive approach simple because we can just check at every-stop whether we have enough seats to allow the passengers into our vehicle? Let's check it out !!
Brute Force Approach
Intuition
Imagine you are a taxi driver who has to drive for 1000km today and our car can carry a certain number of passengers. Each passenger wants to get in at one point and get out at another. But your car can only carry limited number of passengers in the car.
But, how you we figure out if all the passengers can fit during the ride:
What is the first intuitive thought that came to our mind ?
For each group of passengers, we can check when they get in and when they get out.
As we drive, every time passengers get in, we count them. When they get out, w e take them away from our count.
At every point, we will check if the car is too full. If it ever goes over the limit, we stop because it's out of limit !!
For Example: 2 passengers get in at km 1 and get out at km 5. 3 more passengers get in at km 3 and get out at km 7.
At km 3, you already have 2 passengers from before, and now 3 more want to get in. That's 5 passengers! If your car can only hold 4, you can’t take them all.
But if your car can hold 5 or more, you're good to go.
So, we keep counting passengers and check if our car can handle them all during the whole trip! This was the naive approach and now let's see how we can code it up !!
Approach
Initialize an array locations of size 1001, all set to 0.
For each trip in the trips list:
- Extract the number of passengers, start location, and end location.
- For each location from start to end - 1: Increment the passenger count at the current location by the number of passengers.
For each location i from 0 to 1000: If the number of passengers at location i exceeds capacity, return False.
Return the Result: Return True if no location exceeds the capacity.
Dry-Run
trips: [[2, 1, 5], [3, 3, 7], [5, 6, 8]]
capacity: 5
Explanation: The number of passengers at location 6 exceeds the capacity (8 > 5), the function returns false.
Initialize the passengers array:
We create an array locations of size 1001 (indexing from 0 to 1000), initialized to 0. This array will track the number of passengers at each location.
First trip: [2, 1, 5]
Passengers = 2, Start = 1, End = 5.
For locations from 1 to 4 (inclusive of 1, exclusive of 5), increment the passenger count by 2.
- locations[1] += 2 → locations[1] = 2
- locations[2] += 2 → locations[2] = 2
- locations[3] += 2 → locations[3] = 2
- locations[4] += 2 → locations[4] = 2
After processing the first trip, the locations array looks like:
[0, 2, 2, 2, 2, 0, 0, 0, 0, ..., 0]
Second trip: [3, 3, 7]
Passengers = 3, Start = 3, End = 7.
For locations from 3 to 6 (inclusive of 3, exclusive of 7), increment the passenger count by 3.
- locations[3] += 3 → locations[3] = 5
- locations[4] += 3 → locations[4] = 5
- locations[5] += 3 → locations[5] = 3
- locations[6] += 3 → locations[6] = 3
After processing the second trip, the locations array looks like:
[0, 2, 2, 5, 5, 3, 3, 0, 0, ..., 0]
Third trip: [5, 6, 8]
Passengers = 5, Start = 6, End = 8.
For locations from 6 to 7 (inclusive of 6, exclusive of 8), increment the passenger count by 5.
- locations[6] += 5 → locations[6] = 8
- locations[7] += 5 → locations[7] = 5
After processing the third trip, the locations array looks like:
[0, 2, 2, 5, 5, 3, 8, 5, 0, ..., 0]
Check if any location exceeds capacity:
We loop through the locations array from index 0 to 1000.
For each location, check if the passenger count exceeds the capacity of 5:
- At index 0: locations[0] = 0, no issue.
- At index 1: locations[1] = 2, no issue.
- At index 2: locations[2] = 2, no issue.
- At index 3: locations[3] = 5, no issue.
- At index 4: locations[4] = 5, no issue.
- At index 5: locations[5] = 3, no issue.
- At index 6: locations[6] = 8 → Exceeds capacity, return false.
Since the number of passengers at location 6 exceeds the capacity (8 > 5), the function returns false.
Final Result: The answer is false because at location 6, the passengers exceed the capacity.
Brute Force in all Languages
1. C++ Try on Compiler
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<int> locations(1001, 0);
for (auto& trip : trips) {
int passenger = trip[0];
int start = trip[1];
int end = trip[2];
for (int i = start; i < end; i++) {
locations[i] += passenger;
}
}
for (int i = 0; i < 1001; i++) {
if (locations[i] > capacity) {
return false;
}
}
return true;
}
};
2. Java Try on Compiler
class Solution {
// Function to check if car pooling is possible
public boolean carPooling(int[][] trips, int capacity) {
// Initialize an array to track passengers at each location
int locations[] = new int[1001];
// Loop through each trip and update passenger count at locations
for (int[] trip : trips) {
int passenger = trip[0]; // Number of passengers
int start = trip[1]; // Start location
int end = trip[2]; // End location
// For each location between start and end (exclusive of end), add passengers
for (int i = start; i < end; i++) {
locations[i] += passenger;
}
}
// Check if the number of passengers at any location exceeds the capacity
for (int i = 0; i < 1001; i++) {
if (locations[i] > capacity) {
return false; // Return false if capacity is exceeded
}
}
// Return true if the carpooling is possible without exceeding capacity
return true;
}
}
3. Python Try on Compiler
class Solution:
def carPooling(self, trips, capacity):
locations = [0] * 1001
for trip in trips:
passenger = trip[0]
start = trip[1]
end = trip[2]
for i in range(start, end):
locations[i] += passenger
for i in range(1001):
if locations[i] > capacity:
return False
return True
4. JavaScript Try on Compiler
var carPooling = function(trips, capacity) {
let locations = new Array(1001).fill(0);
for (let trip of trips) {
let passenger = trip[0];
let start = trip[1];
let end = trip[2];
for (let i = start; i < end; i++) {
locations[i] += passenger;
}
}
for (let i = 0; i < 1001; i++) {
if (locations[i] > capacity) {
return false;
}
}
return true;
};Time Complexity: O(n*m)
There are n trip in trips array and each array of the trip[] can have 1 as start and 1000 as end. So, the computation take n*m time complexity which is : O(n*m) where n is the no of trips , and m is the
Iterating the locations[] takes O(n) time at max to find the result which additionally takes O(n) runtime.
The overall Time Complexity is : O(n*m)
Space Complexity: O(n)
Auxiliary space complexity refers to the extra space used by the algorithm excluding the input space.
In this case: The main extra space is used by the locations array, which is of size n i.e. 1001.
The trips array is part of the input and does not count towards auxiliary space.
Thus, the auxiliary space complexity is O(n), which is O(1) since it's a constant value and does not grow with the input size.
Total Space Complexity
Input : We take n trip inputs with each trip with 3 elements. So, it takes O(3n) space which equals O(n)
Auxiliary space complexity: O(n)
The overall space complexity is O(n) + O(n) = O(2n) = O(n)
Did we just observe that we are repeatedly running loops for each trip[] of passengers and checking the no of passengers it could carry ? It took extra runtime which may lead to Time Limt Exceeded in case of larger constraints. Let's see how we can optimize it further !
Optimal Approach
Intuition
When a trip starts at a location, passengers get on the car. When the trip ends at another location, passengers get off the car. So, every time a person gets on or off, we just need to remember this change at those specific locations. These two key events are where the changes in the number of passengers happen.
So, instead of tracking every location, we can focus on: Adding passengers when they get on at the start location and Removing passengers when they get off at the end location.
Why We Only Need to Track Changes at Start and End Locations ?
At the start of each trip, passengers board the car, and at the end, they leave the car. Therefore at a start location,we know exactly how many passengers are entering the car. At an end location, we know exactly how many passengers are exiting the car.
With this insight, we realized that the car's capacity will only ever be impacted by the start and end locations of trips, not by the locations in between. So, instead of updating the number of passengers at every location between the start and end for each trip, we only need to:
- Add passengers at the start of each trip.
- Remove passengers at the end of each trip.
What does it mean? It will take O(1) time to add passenger at start i.e locations[start] and O(1) time to remove/subtract passengers at end i.e. locations[end] resulting in O(1) + O(1) = O(1),
Do you remember that we used two nested loops to fill the locations[] which resulted in O(n^2) runtime. O(1) is much faster.
This leads us to the idea of tracking changes at each location rather than simulating the entire journey.
As we move through the list of locations, we keep a running total of how many passengers are in the car at that location.
What ?? A running Total ?? Are, we unknowingly speaking about prefix-sum approach ?? Yes !!
We track changes at the start and end of each trip. Then, as we sweep through all the locations, we apply the cumulative sum (prefix sum) to see how the number of passengers changes over time. This is nothing but the line sweep algorithm.
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.
But, how can we apply this to the optimal solution.
For each trip, we only mark where passengers get on and get off: If 3 people get on at location 2, we add 3 to locations[2]. If the same 3 people get off at location 5, we subtract 3 from locations[5].
Now, we just sweep through the locations and keep a running total of how many passengers are in the car at each location. If at any location, currentPassengers exceeds the car’s capacity, we know it’s not possible to fit all passengers, and we return false. If we can go through all locations without exceeding the capacity, then the carpool is possible, and we return true.
Let's see how we can code it up !!
Approach
Initialize a list locations of size 1001 with all elements set to 0 (this tracks changes in the number of passengers at each location).
For each trip in trips: Extract the number of passengers, start location, and end location. Add the number of passengers to locations[start]. Subtract the number of passengers from locations[end].
Initialize a variable currentPassengers to 0.
For each location from 0 to 1000: Update currentPassengers by adding locations[i]. If currentPassengers exceeds capacity, return false (indicating the car can't complete all trips within capacity).
If all locations are processed without exceeding the capacity, return true (indicating all trips can be completed).
Dry-Run
trips: [[2, 1, 5], [3, 3, 7], [5, 6, 8]]
capacity: 5
Explanation: The number of passengers at location 6 exceeds the capacity (8 > 5), the function returns false.
Step 1: Initialization
- Create an array locations of size 1001 (all zeros).
- currentPassengers = 0 (to track the running total of passengers).
Step 2: Process Each Trip (Update locations)
Trip [2, 1, 5] – 2 passengers from location 1 to 5:
- locations[1] += 2 → Add 2 passengers at location 1.
- locations[5] -= 2 → Remove 2 passengers at location 5.
- locations: [0, 2, 0, 0, 0, -2, 0, 0, ...]
Trip [3, 3, 7] – 3 passengers from location 3 to 7:
- locations[3] += 3 → Add 3 passengers at location 3.
- locations[7] -= 3 → Remove 3 passengers at location 7.
- locations: [0, 2, 0, 3, 0, -2, 0, -3, ...]
Trip [5, 6, 8] – 5 passengers from location 6 to 8:
- locations[6] += 5 → Add 5 passengers at location 6.
- locations[8] -= 5 → Remove 5 passengers at location 8.
- locations: [0, 2, 0, 3, 0, -2, 5, -3, -5, ...]
Step 3: Line Sweep (Prefix Sum)
Iterate over each location (from 0 to 1000):
- Location 0: currentPassengers = 0 → No change.
- Location 1: currentPassengers += 2 → 2 (No, within capacity).
- Location 3: currentPassengers += 3 → 5 (No, at capacity).
- Location 5: currentPassengers -= 2 → 3 (No, below capacity).
- Location 6: currentPassengers += 5 → 8 → Exceeds capacity!
Step 4: Result: Since the capacity is exceeded at location 6, return false.
Optimal Code in all Languages
1. C++ Try on Compiler
// Car Pooling function to check if trips can be completed within capacity
bool carPooling(vector<vector<int>>& trips, int capacity) {
// Array to track passenger changes at each location
vector<int> locations(1001, 0);
// Update locations based on each trip
for (auto& trip : trips) {
int numPassengers = trip[0]; // Number of passengers
int start = trip[1]; // Start location
int end = trip[2]; // End location
// Add passengers at start location
locations[start] += numPassengers;
// Remove passengers at end location
locations[end] -= numPassengers;
}
// Track current passengers
int currentPassengers = 0;
// Check each location to see if capacity is exceeded
for (int i = 0; i < 1001; i++) {
// Update current passengers
currentPassengers += locations[i];
// Return false if capacity is exceeded
if (currentPassengers > capacity) {
return false;
}
}
// Return true if within capacity
return true;
}2. Java Try on Compiler
class Solution {
// Car Pooling function to check if all trips can be accommodated within capacity
public boolean carPooling(int[][] trips, int capacity) {
// Create an array to track passenger changes at each location
int[] locations = new int[1001]; // Max location is 1000, array size 1001
// Loop through each trip to update locations array
for (int[] trip : trips) {
int numPassengers = trip[0]; // Number of passengers in the current trip
int start = trip[1]; // Start location of the trip
int end = trip[2]; // End location of the trip
// Add passengers at the starting location
locations[start] += numPassengers;
// Remove passengers at the ending location
locations[end] -= numPassengers;
}
// Track current passengers at each point
int currentPassengers = 0;
// Iterate through all locations to check if capacity is exceeded
for (int i = 0; i < locations.length; i++) {
// Update the current passenger count
currentPassengers += locations[i];
// If capacity is exceeded at any point, return false
if (currentPassengers > capacity) {
return false;
}
}
// Return true if capacity is never exceeded
return true;
}
}
3. Python Try on Compiler
def carPooling(trips, capacity):
# Create an array to track passenger changes at each location
locations = [0] * 1001
# Update locations based on trips
for trip in trips:
numPassengers = trip[0] # Number of passengers
start = trip[1] # Start location
end = trip[2] # End location
# Add passengers at start location
locations[start] += numPassengers
# Remove passengers at end location
locations[end] -= numPassengers
# Track current passengers
currentPassengers = 0
# Check each location to see if capacity is exceeded
for passengerChange in locations:
# Update current passengers
currentPassengers += passengerChange
# Return false if capacity is exceeded
if currentPassengers > capacity:
return False
# Return true if within capacity
return True
4. JavaScript Try on Compiler
var carPooling = function(trips, capacity) {
// Create an array to track passenger changes at each location
let locations = new Array(1001).fill(0);
// Update locations based on each trip
for (let trip of trips) {
let numPassengers = trip[0]; // Number of passengers
let start = trip[1]; // Start location
let end = trip[2]; // End location
// Add passengers at start location
locations[start] += numPassengers;
// Remove passengers at end location
locations[end] -= numPassengers;
}
// Track current passengers
let currentPassengers = 0;
// Check each location to see if capacity is exceeded
for (let i = 0; i < locations.length; i++) {
// Update current passengers
currentPassengers += locations[i];
// Return false if capacity is exceeded
if (currentPassengers > capacity) {
return false;
}
}
// Return true if within capacity
return true;
};Time Complexity: O(n)
Processing Trips (First Loop): The loop for iterates through all trips for n times to mark into the arrays which takes O(n)
Traversing the locations[]:
We need O(n) time to traverse the location array and calculate the prefix sum.
So, the overall time complexity is O(n) + O(n)= O(2n) = O(n)
Space Complexity: O(n)
Auxiliary Space Complexity refers to the extra space required in the algorithm excluding the input space.
locations [] : we are using locations[] array of size n, hence it accumulates O(n) space.
We use currentPassengers variable for the accumulating sum which accounts for O(1) space.
The total auxiliary space complexity is: O(1) + O(n) = O(n)
Total Space Complexity:
trips[][] consumes 2d-array of n size and each array has 3 integers, which all total accumulates to O(3n)= O(n)
Auxiliary space complexity: O(n)
Overall total space complexity is: O(n) + O(n)= O(2n)= O(n)
Learning Tip
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.
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.