DSA problem
Car Pooling
There is a car with capacity empty seats. It travels east, only forward, never backward. Given a list of trips trips[i] = [numPassengers_i, from_i, to_i] where each trip picks up numPassengers_i passengers at location from_i and drops them at location to_i, return true if and only if the car can make every trip without ever exceeding capacity.
The key observation is that the car's occupancy is purely a function of location, not time, and changes only at the pickup and dropoff points of each trip. Between events the occupancy is constant. This means the problem is equivalent to scanning a stream of "add" and "subtract" events ordered by position and checking the running sum.
The classic tool for this kind of cumulative event problem is the difference array (or imbalance array). Allocate an array delta of length maxLocation + 1. For each trip, increment delta[from] by numPassengers and decrement delta[to] by numPassengers — note we subtract at to because passengers leave exactly at the drop location, freeing those seats before any pickup that also happens at to.
Then compute the prefix sum left to right. The value at each position is the current occupancy of the car after all events at or before that position have been processed. If the prefix sum ever exceeds capacity the answer is false; otherwise it is true. Total complexity is O(n + maxLocation) time and O(maxLocation) space; constraints make this trivially fast because to_i <= 1000.
Examples
trips = [[2,1,5],[3,3,7]], capacity = 4falsetrips = [[2,1,5],[3,3,7]], capacity = 5truetrips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11trueConstraints
- 1 <= trips.length <= 1000
- trips[i].length == 3
- 1 <= numPassengers_i <= 100
- 0 <= from_i < to_i <= 1000
- 1 <= capacity <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.