Car Pooling
Problem statement
A car has capacity empty seats and only drives forward (east). Each trip [passengers, from, to] picks up passengers people at kilometre from and drops them off at kilometre to. At any location, people getting off leave before new people get on.
Return true if the car can complete every trip without ever carrying more than capacity people, and false otherwise.
This is the same check as "do these jobs ever need more than N slots at once?": each job holds some slots from its start time to its end time, and you want to know whether the peak ever goes over the limit — for a connection pool, a set of build runners, or a rate-limited API.
Examples
Example 1
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Explanation: Between kilometre 3 and 5 both trips are in the car at the same time, so it carries 2 + 3 = 5 people. That is more than the 4 seats.
Example 2
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
Explanation: The busiest stretch is still 5 people, between kilometre 3 and 5. With 5 seats that just fits, and the load drops to 3 once the first group gets off at kilometre 5.
Hints
Approach
Optimal: Difference array
Intuition
Take the event idea one step further. Locations are small whole numbers (0 to 1,000), so instead of sorting events, drop each change straight into a list indexed by location: diff[from] += passengers and diff[to] -= passengers. This list is a difference array — it stores how the load changes at each location, not the load itself.
Now walk from location 0 upward, keeping a running total (a prefix sum) of diff. At each location, that running total is exactly the number of people in the car. Drop-offs are handled correctly too: the minus at to and any plus at to are added together in the same slot, so a group getting off and another getting on at the same place never overlap. If the running total ever exceeds capacity, return false.
Steps
- Create
diff, a list of 1,001 zeros (one per possible location). - For each trip
[p, from, to]:diff[from] += panddiff[to] -= p. - Set
load = 0. For each location from 0 to 1,000: adddiff[location]toload; ifload > capacity, returnfalse. - Return
true.
Dry run
Example 1, capacity = 4: after step 2, diff[1] = +2, diff[3] = +3, diff[5] = −2, diff[7] = −3, everything else 0.
| location | diff | load after | over 4? |
|---|---|---|---|
| 0 | 0 | 0 | no |
| 1 | +2 | 2 | no |
| 2 | 0 | 2 | no |
| 3 | +3 | 5 | yes → return false |
With capacity = 5, the load goes 0, 2, 2, 5, 5, 3, 3, 0 and never exceeds 5 → true.
Complexity
Time O(T + L) - Recording the two changes per trip costs O(T). One left-to-right pass over the route to build the running total costs O(L), with L at most 1,001 locations here. There is no sorting. For 1,000 trips on a 1,000 km route that is about 3,000 steps.
Space O(L) - The difference array has one slot per location, so 1,001 numbers here. That is fixed and small because locations are limited to 1,000. The input is not counted.
from typing import List
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
diff = [0] * 1001
for p, start, to in trips:
diff[start] += p
diff[to] -= p
load = 0
for change in diff:
load += change
if load > capacity:
return False
return True
if __name__ == "__main__":
print(str(Solution().carPooling([[2, 1, 5], [3, 3, 7]], 4)).lower()) # false
print(str(Solution().carPooling([[2, 1, 5], [3, 3, 7]], 5)).lower()) # trueRecapThe whole problem in a few lines, for the night before
- Spot it: many intervals each add a load over a range; "is the total ever over a limit?"
- Idea: difference array —
+pat start,-pat end, then a running total gives the load at every point - Cost: O(T + L) time, O(L) space (sorted events: O(T log T), for large or sparse locations)
- Trap: subtracting at
to + 1instead ofto— people get off before others get on - Remember: at the same location, drop-offs before pickups; sorting
(location, change)does that automatically
Interview follow-ups
Return the highest load reached, not just true or false.
Keep the same running total and track its maximum instead of comparing with
capacity. The answer is that maximum. Time and space stay the same. In infra terms, this is the peak concurrency number you'd put on a capacity-planning dashboard.Locations are timestamps up to 10¹², and there are 10⁶ trips.
A difference array with 10¹² slots is impossible, so use the sorted-events approach: 2 × 10⁶ events, sorted in O(T log T). If the events already arrive in time order (as in a log), you don't even need to sort — just keep the running total as you read. Memory stays O(T) or even O(1) for the streaming case.
Trips arrive one by one, and you must reject any trip that would go over capacity.
Keep the load per location in a structure that supports "add
pto a range" and "what is the maximum over a range?". For small routes, a plain array checked over[from, to)is O(L) per trip and fine. For big routes, a balanced tree of events (sorted by location) or a segment tree makes each check O(log L); in an interview, describing the plain array first and naming the faster structure is enough.
Frequently asked questions
It is a list that stores changes instead of values. To add x to every position from a up to (not including) b, you write +x at a and -x at b — two updates instead of b - a. A running total (prefix sum) over the list then rebuilds the actual values. It turns many range updates into one cheap pass.
Passengers are dropped off before new ones are picked up at the same spot, so at kilometre to they are already gone. Subtracting at to removes them exactly there. If you subtracted at to + 1, a group leaving at 5 would still count at 5, and back-to-back trips would wrongly look like they overlap.
When locations are huge or sparse, like Unix timestamps or byte offsets. A difference array needs one slot per possible location, which could be billions. Sorted events need only two entries per trip, whatever the locations are. Here locations stop at 1,000, so the array is smaller and faster.
Yes. Sort trips by pickup point, and keep a min-heap of active trips ordered by drop-off point. Before each pickup, pop every trip that ends at or before it and subtract its passengers. That is also O(T log T), like the sorted events, and it matches the classic "meeting rooms" pattern. The sweep line is shorter to write.
It's peak-concurrency checking. Replace trips with jobs, requests or reservations that hold a resource from a start time to an end time, and capacity with the number of slots, connections or licences. "Did we ever exceed N at once?" is a standard capacity-planning and incident question, and this is the standard answer.