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] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi 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.
Example 1:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4 Output: false
Example 2:
Input: trips = [[2,1,5],[3,3,7]], capacity = 5 Output: true
Constraints:
1 <= trips.length <= 1000trips[i].length == 31 <= numPassengersi <= 1000 <= fromi < toi <= 10001 <= capacity <= 105The key idea in #1094 Car Pooling is to track how the number of passengers in the car changes along the route. Each trip specifies passengers, a pickup point, and a drop-off point. Instead of simulating every mile, you can model these as passenger changes at specific locations.
A common approach is the prefix sum (difference array) technique. For each trip, increase passengers at the pickup location and decrease them at the drop-off location. By computing a running sum across locations, you can detect if the number of passengers ever exceeds the car's capacity.
Another approach is to sort trips by start location and use a min-heap to track upcoming drop-offs. As the car moves forward, remove completed trips from the heap and add new passengers, ensuring the total never exceeds capacity.
Both strategies efficiently simulate passenger flow along the route. The prefix sum method is particularly clean and runs in linear time relative to the location range.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Sum / Difference Array | O(n + m) | O(m) |
| Sorting + Min Heap Simulation | O(n log n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Sort the pickup and dropoff events by location, then process them in order.
We can simulate the number of passengers in the car at each kilometer using a difference array. For each trip, increase the passenger count at fromi and decrease it at toi. Then, iterate through this array to calculate the actual number of passengers at each point, checking if it ever exceeds the capacity.
Time Complexity: O(n + m) where n is the number of trips and m is the max distance (1000).
Space Complexity: O(m) for the difference array.
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 bool carPooling(std::vector<std::vector<int>>& trips, int capacity) {
7 int passengerChanges[1001] = {0};
8
9 for(const auto& trip : trips) {
10 passengerChanges[trip[1]] += trip[0];
11 passengerChanges[trip[2]] -= trip[0];
12 }
13
14 int currentPassengers = 0;
for(int i = 0; i < 1001; ++i) {
currentPassengers += passengerChanges[i];
if (currentPassengers > capacity) return false;
}
return true;
}
};Similar to the C implementation, we use a difference array for passenger changes. The core logic processes trips to adjust the difference array and then checks cumulative passengers against capacity.
In this approach, we treat each pick-up and drop-off as events. We collect all events, sort them based on location, and then simulate the process of picking up and dropping off passengers by iterating through events in order, checking if it ever exceeds the car's capacity.
Time Complexity: O(n log n), driven by sorting events.
Space Complexity: O(n).
1using System;
using System.Collections.Generic;
public class Solution {
public bool CarPooling(int[][] trips, int capacity) {
List<int[]> events = new List<int[]>();
foreach (var trip in trips) {
events.Add(new int[]{trip[1], trip[0]}); // pickup
events.Add(new int[]{trip[2], -trip[0]}); // drop-off
}
events.Sort((a, b) => a[0] - b[0]);
int currentPassengers = 0;
foreach (var ev in events) {
currentPassengers += ev[1];
if (currentPassengers > capacity) return false;
}
return true;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Car Pooling is a common medium-level interview problem that tests array manipulation, sweep line logic, and priority queue usage. Variations of interval or capacity tracking problems frequently appear in FAANG-style interviews.
The optimal approach often uses a prefix sum (difference array) technique. By marking passenger pickups and drop-offs at specific locations and computing a running sum, you can quickly detect if the passenger count exceeds the car's capacity.
A difference array combined with prefix sums works very well for this problem. Alternatively, a min-heap (priority queue) can be used to track the earliest drop-off times while processing trips sorted by pickup location.
The prefix sum approach works because passenger changes only occur at pickup and drop-off points. By recording these changes and computing cumulative totals along the route, you can simulate the number of passengers at any point efficiently.
Carrying each trip as event-based modifications, we sort and manage updates correspondingly to ensure no overcapacity occurs.