LC 1094: Car Pooling
LC 1094: Car Pooling
Difficulty: Medium
Category: Array, Sorting, Simulation
Companies: Amazon, Google, Microsoft, Uber
Problem Statement
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, from, to] indicates that the i-th trip has numPassengers passengers and the locations to pick them up and drop them off are from and to 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
Example 1:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Explanation:
- Trip 1: Pick up 2 passengers at location 1, drop off at location 5
- Trip 2: Pick up 3 passengers at location 3, drop off at location 5
- At location 3, we have 2 + 3 = 5 passengers, which exceeds capacity (4)
Example 2:
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
Explanation:
- Trip 1: Pick up 2 passengers at location 1, drop off at location 5
- Trip 2: Pick up 3 passengers at location 3, drop off at location 5
- At location 3, we have 2 + 3 = 5 passengers, which equals capacity (5)
Constraints
1 <= trips.length <= 1000trips[i].length == 31 <= numPassengers <= 1000 <= from < to <= 1000
Solution Approaches
Approach 1: Bucket Sort with Timestamps (Recommended)
Key Insight: Use a bucket array to track passenger changes at each timestamp. Add passengers at pickup locations and subtract at drop-off locations.
Algorithm:
- Create a timestamp array of size 1001 (since locations are 0-1000)
- For each trip, add passengers at pickup location and subtract at drop-off location
- Iterate through timestamps and track cumulative passengers
- Return false if capacity is exceeded at any point
Time Complexity: O(n + 1001) = O(n)
Space Complexity: O(1001) = O(1)
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<int> timestamp(1001);
for(auto& trip: trips) {
timestamp[trip[1]] += trip[0]; // Pick up passengers
timestamp[trip[2]] -= trip[0]; // Drop off passengers
}
int usedCapacity = 0;
for(int number: timestamp) {
usedCapacity += number;
if(usedCapacity > capacity) {
return false;
}
}
return true;
}
};
Approach 2: Sorting with Events
Algorithm:
- Create events for pickup and drop-off
- Sort events by location
- Process events in order and track passengers
- Return false if capacity exceeded
Time Complexity: O(n log n)
Space Complexity: O(n)
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<pair<int, int>> events; // {location, passenger_change}
for(auto& trip: trips) {
events.push_back({trip[1], trip[0]}); // Pick up
events.push_back({trip[2], -trip[0]}); // Drop off
}
sort(events.begin(), events.end());
int usedCapacity = 0;
for(auto& event: events) {
usedCapacity += event.second;
if(usedCapacity > capacity) {
return false;
}
}
return true;
}
};
Approach 3: Simulation with Priority Queue
Algorithm:
- Sort trips by pickup location
- Use priority queue to track active trips
- Process trips in order and manage drop-offs
- Check capacity at each pickup
Time Complexity: O(n log n)
Space Complexity: O(n)
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
sort(trips.begin(), trips.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1]; // Sort by pickup location
});
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int usedCapacity = 0;
for(auto& trip: trips) {
int passengers = trip[0];
int pickup = trip[1];
int dropoff = trip[2];
// Drop off passengers who have reached their destination
while(!pq.empty() && pq.top().first <= pickup) {
usedCapacity -= pq.top().second;
pq.pop();
}
// Pick up new passengers
usedCapacity += passengers;
if(usedCapacity > capacity) {
return false;
}
// Add drop-off event
pq.push({dropoff, passengers});
}
return true;
}
};
Algorithm Analysis
Approach Comparison
| Approach | Time | Space | Pros | Cons |
|---|---|---|---|---|
| Bucket Sort | O(n) | O(1) | Optimal, simple | Limited to small ranges |
| Sorting Events | O(n log n) | O(n) | General purpose | More complex |
| Priority Queue | O(n log n) | O(n) | Handles complex cases | Overkill for this problem |
Key Insights
- Bucket Sort Advantage: Most efficient for small, bounded ranges
- Event Processing: Treat pickup and drop-off as separate events
- Cumulative Tracking: Track running total of passengers
- Early Termination: Stop as soon as capacity is exceeded
Implementation Details
Bucket Sort Technique
// Add passengers at pickup location
timestamp[trip[1]] += trip[0];
// Remove passengers at drop-off location
timestamp[trip[2]] -= trip[0];
Event Processing
// Process events in chronological order
for(int number: timestamp) {
usedCapacity += number;
if(usedCapacity > capacity) return false;
}
Edge Cases
- Single Trip:
[[1,0,1]]with capacity 1 → true - No Trips:
[]with any capacity → true - Exact Capacity: Passengers exactly equal capacity → true
- Overlapping Trips: Multiple trips at same location → check total
Follow-up Questions
- What if locations could be very large (up to 10^9)?
- How would you handle multiple cars?
- What if passengers could be picked up and dropped off at the same location?
- How would you optimize for very large numbers of trips?
Related Problems
Optimization Techniques
- Bucket Sort: Use array indexing for small ranges
- Event-Based Processing: Treat state changes as events
- Early Termination: Stop processing when constraint violated
- Space Optimization: Use fixed-size arrays when possible
Code Quality Notes
- Readability: Bucket sort approach is most intuitive
- Performance: O(n) time complexity is optimal
- Scalability: Sorting approach works for any range
- Robustness: All approaches handle edge cases correctly
This problem demonstrates the power of bucket sort for small, bounded ranges and shows how event-based processing can simplify complex simulation problems.