Car Pooling: Difference Array Sweep Line
You are driving a vehicle that has capacity seats. You are given an array trips where trips[i] = [numPassengers, from, to] means that numPassengers passengers board at stop from and exit at stop to. Return true if you can pick up and drop off all passengers without ever exceeding capacity, or false otherwise.
This is LeetCode 1094: Car Pooling, a medium problem that rewards you for knowing the difference array technique. Instead of simulating each trip individually, you can encode all boarding and exiting events in a single array and sweep through it once.
Why this problem matters
Car pooling is one of the cleanest introductions to the difference array pattern. The idea is simple: rather than updating every stop along a trip's range, you mark only the start and end of each range. A single prefix sum pass then reconstructs the full picture. This turns what could be an O(n * m) brute force into an O(n + m) solution.
The same technique shows up in a wide variety of problems: range update queries, flight booking totals, meeting room scheduling, and any scenario where you need to track how many overlapping intervals are active at each point. Once you internalize the pattern, you will recognize it immediately.
Car pooling also connects to the sweep line family of algorithms. You are essentially sweeping from the first stop to the last, accumulating events as you go. The difference array is the discrete version of the sweep line, and understanding one helps you understand the other.
The key insight
Instead of incrementing every stop between from and to for each trip, use a difference array. For a trip [num, from, to], add +num at index from and -num at index to. This records the net change in passengers at each stop boundary.
After processing all trips, compute the prefix sum of the difference array. At each index, the prefix sum tells you exactly how many passengers are on the vehicle. If that number ever exceeds capacity, return false.
The key observation is that passengers who board at stop from and exit at stop to are not on the vehicle at stop to. They leave before you pick up anyone else at that stop. This is why you subtract at index to, not to + 1.
The solution
def car_pooling(trips, capacity):
diff = [0] * 1001
for num, start, end in trips:
diff[start] += num
diff[end] -= num
current = 0
for d in diff:
current += d
if current > capacity:
return False
return True
The solution has two phases. First, you build the difference array by iterating through every trip and recording the boarding (+num) and exiting (-num) events. Second, you sweep through the array computing a running sum. This running sum is the actual passenger count at each stop. The moment it exceeds capacity, you return false.
The constraint says stops go up to 1000, so a fixed-size array of 1001 elements works. You could also find the maximum stop value from the trips and use that as the array size for a tighter bound.
The difference array trick works because addition distributes over prefix sums. Recording +num at the start and -num at the end is equivalent to adding num to every index in the range, but it takes O(1) per trip instead of O(range length).
Visual walkthrough
Step 1: Initialize the difference array
Create an array of size max_stop + 1, initialized to zeros. Here max stop is 7.
Step 2: Process trip [2, 1, 5]
Add +2 at stop 1 (boarding) and -2 at stop 5 (exiting). Passengers ride during stops 1 through 4.
Step 3: Process trip [3, 3, 7]
Add +3 at stop 3 (boarding) and -3 at stop 7 (exiting). Both trips are now encoded in the diff array.
Step 4: Compute prefix sums (sweep line)
Running sum gives the actual passenger count at each stop. Stop 3 has count 5, which exceeds capacity 4.
Step 5: Check against capacity
Stops 3 and 4 both have 5 passengers, exceeding capacity of 4. Return false.
The walkthrough uses trips = [[2,1,5],[3,3,7]] with capacity = 4. After building the difference array, the prefix sum reveals that stops 3 and 4 have 5 passengers each, which exceeds the capacity of 4. The answer is false.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Difference array | O(n + m) | O(m) |
Time: O(n + m) where n is the number of trips and m is the maximum stop value. You iterate through all n trips to build the difference array (O(n)), then sweep through m stops to compute prefix sums (O(m)).
Space: O(m) for the difference array. Since stops are bounded by 1000 in this problem, you can treat this as O(1) with respect to input size, but conceptually it scales with the stop range.
The building blocks
1. Difference array for range updates
The difference array is a technique for applying range updates in O(1) per update. Instead of modifying every element in a range, you modify only the endpoints:
diff[start] += value
diff[end] -= value
After all updates, a prefix sum over diff gives you the actual values. This is the core building block behind car pooling, flight booking problems, and range-increment queries.
2. Prefix sum scan
The prefix sum converts the difference array back into actual counts:
current = 0
for d in diff:
current += d
At each step, current holds the sum of all differences up to that index, which equals the total number of active passengers. This scan is where you check the capacity constraint. The prefix sum is one of the most versatile building blocks in algorithm problems, appearing in subarray sums, range queries, and cumulative statistics.
Edge cases
- Single trip that exactly fills capacity:
trips = [[4,0,5]], capacity = 4should returntrue. The count equals capacity but does not exceed it. - Multiple trips at the same stop: several groups can board at the same stop. The difference array handles this naturally since you just add all deltas at that index.
- Trip with zero length: a trip where
from == towould add and subtract at the same index, contributing nothing. The constraints guaranteefrom < to, but it is good to know the math is safe. - All trips overlap at one point: if every trip passes through the same stop, the difference array accumulates all of them there. This is the worst case for capacity.
- Capacity of 1: the tightest constraint. Only one passenger can be on board at any time, so no two trips can overlap.
From understanding to recall
You have seen the difference array solution and it makes sense. Two lines to build the array, one loop to sweep. But the details matter: subtracting at end (not end + 1), checking greater than capacity (not greater than or equal), and initializing the array to the right size.
Under interview pressure, these small decisions are where mistakes happen. You might second-guess whether to subtract at to or to - 1. You might forget to sweep all the way to the end. Spaced repetition removes that uncertainty. After a few rounds of writing the solution from scratch, the pattern becomes automatic.
The difference array is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning it in isolation and drilling it with spaced repetition is far more effective than encountering it once inside a problem and hoping you remember it months later.
Related posts
- Meeting Rooms II - Count overlapping intervals to find the minimum number of conference rooms
- Insert Interval - Merge a new interval into a sorted list of non-overlapping intervals
- Merge Intervals - Combine overlapping intervals into a minimal set
CodeBricks breaks the car pooling LeetCode problem into its difference array and prefix sum building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When an interval or sweep line question comes up in your interview, you do not hesitate. You just write it.