Car Pooling
Problem
Given an array trips where trips[i] = [numPassengers, startLocation, endLocation] and an integer capacity, return true if it is possible to pick up and drop off all passengers for all the given trips without exceeding the vehicle capacity at any point, otherwise return false.
- 1 ≤ trips.length ≤ 1000
- trips[i].length == 3
- 1 ≤ numPassengers ≤ 100
- 0 ≤ startLocation < endLocation ≤ 1000
- 1 ≤ capacity ≤ 10⁵
Example
trips = [[2,1,5],[3,3,7]], capacity = 4falseThe vehicle picks up 2 passengers at location 1 and drops them off at location 5. It also picks up 3 passengers at location 3 and drops them off at location 7. Between locations 3 and 5, the vehicle carries 5 passengers, exceeding the capacity of 4, so the output is false.
Approach
Straightforward Solution
A naive approach simulates the vehicle's journey step-by-step, updating the passenger count at every location between start and end for each trip. This approach is O(n * d), where d is the distance range, which is inefficient for large inputs.
Core Observation
The number of passengers changes only at discrete locations where passengers are picked up or dropped off. Tracking the net change in passengers at each location allows efficient computation of the current load at any point.
Path to Optimal
Recognizing that passenger changes occur only at trip start and end points, the problem can be transformed into a difference array or prefix sum problem. By recording increments at start locations and decrements at end locations, a single pass accumulation yields the passenger count at each location efficiently.
Optimal Approach
Create an array representing all possible stops (0 to 1000). For each trip, add the number of passengers at the start index and subtract at the end index. Then, iterate through the array accumulating passenger counts. If at any point the accumulated count exceeds capacity, return false. Otherwise, return true after the iteration.
Time
O(n + d)
Processing each trip to update the difference array takes O(n), and iterating through the stops array of fixed size (1001) takes O(d), resulting in O(n + d) time complexity.
Space
O(d)
The auxiliary space is O(d) for the stops array, where d is the maximum location index (1001). This space is necessary to track passenger changes at each stop.
Pattern Spotlight
Prefix Sum (Difference Array)
When a problem involves multiple range updates and queries on a linear structure, use a difference array to record incremental changes at boundaries, then compute prefix sums to efficiently reconstruct the full state.
Solution
| 1 | class Solution: |
| 2 | def carPooling(self, trips: List[List[int]], capacity: int) -> bool: |
| 3 | stops = [0] * 1001 |
| 4 | |
| 5 | for num, start, end in trips: |
| 6 | stops[start] += num |
| 7 | stops[end] -= num |
| 8 | |
| 9 | curr = 0 |
| 10 | for x in stops: |
| 11 | curr += x |
| 12 | if curr > capacity: |
| 13 | return False |
| 14 | |
| 15 | return True |
Step-by-Step Solution
Record Passenger Pickups and Drop-offs at Each Location
| 3 | stops = [0] * 1001 |
| 5 | for num, start, end in trips: |
| 6 | stops[start] += num |
| 7 | stops[end] -= num |
Objective
To build a difference array that captures net passenger changes at each stop based on trip data.
Key Insight
By incrementing the passenger count at the start location and decrementing at the end location for each trip, the difference array compactly encodes all passenger changes. This approach avoids simulating every location between start and end, enabling efficient aggregation later.
Interview Quick-Check
Core Logic
Incrementing at start and decrementing at end for each trip encodes passenger changes as a difference array, enabling O(1) updates per trip.
Common Pitfalls & Bugs
Forgetting to decrement at the end location leads to incorrect passenger counts, as passengers must be considered dropped off exactly at that point.
Accumulate Passenger Counts and Validate Capacity Constraints
| 9 | curr = 0 |
| 10 | for x in stops: |
| 11 | curr += x |
| 12 | if curr > capacity: |
| 13 | return False |
Objective
To compute the running total of passengers at each stop and check if capacity is exceeded.
Key Insight
Accumulating the difference array reconstructs the actual passenger count at each location. Checking the capacity constraint during accumulation allows early termination if the vehicle is overloaded, improving efficiency.
Interview Quick-Check
Core Logic
Prefix sum accumulation of the difference array yields the current passenger count at each stop, enabling capacity validation in a single pass.
State & Boundaries
Return false immediately upon exceeding capacity to avoid unnecessary computation.
Common Pitfalls & Bugs
Not accumulating in order or failing to check capacity at each step can lead to incorrect results or missed overloads.
Confirm Feasibility After Processing All Stops
| 15 | return True |
Objective
To return true if the vehicle never exceeds capacity throughout the trip.
Key Insight
If the accumulation completes without detecting an overload, it guarantees that the vehicle can handle all trips within capacity constraints.
Interview Quick-Check
Core Logic
Returning true after full accumulation confirms no capacity violations occurred at any stop.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
if curr > capacity:Check if the current passenger count exceeds vehicle capacity.
This conditional detects overloads immediately, enabling early termination to improve efficiency and correctness.
stops[start] += numAdd the number of passengers picked up at the start location.
Incrementing at the start index records the addition of passengers boarding the vehicle, marking the beginning of their journey.
stops[end] -= numSubtract the number of passengers dropped off at the end location.
Decrementing at the end index records passengers leaving the vehicle, ensuring the difference array accurately reflects net passenger changes.
curr += xUpdate the current passenger count with the net change at this stop.
Adding the difference array value at each stop updates the current load, reflecting pickups and drop-offs accurately.
stops = [0] * 1001Initialize an array to track passenger changes at each stop.
This array acts as a difference array where increments and decrements at specific indices represent passenger pickups and drop-offs, enabling efficient cumulative calculation.
return FalseReturn false if capacity is exceeded at any point.
Returning false here ensures the algorithm halts as soon as an infeasible state is detected, preventing unnecessary computation.
return TrueReturn true if all stops are processed without exceeding capacity.
Completing the iteration without overload confirms the vehicle can handle all trips within capacity constraints, satisfying the problem requirements.
for num, start, end in trips:Iterate over each trip to process passenger changes.
Processing each trip individually allows precise updates to the difference array at the start and end locations, capturing all passenger movements.
for x in stops:Iterate through each stop to accumulate passenger counts.
Sequential iteration over the difference array reconstructs the actual passenger count at each location by summing net changes.
curr = 0Initialize a variable to accumulate current passenger count.
This accumulator will track the running total of passengers on the vehicle as stops are processed sequentially.
Test Your Understanding
Why does using a difference array with prefix sums allow efficient tracking of passenger counts instead of simulating every location for each trip?
Because passenger count changes only at trip start and end points, recording increments and decrements at these boundaries and then accumulating them reconstructs the passenger count at all locations in a single pass, avoiding costly per-location updates for each trip.
Related Problems
Prefix Sum pattern
Don't just read it. Drill it.
Reconstruct Car Pooling from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Car Pooling drill