Car Pooling

Car Pooling asks a deceptively simple scheduling question, and it is the cleanest way to learn the difference array trick — a tool for applying many overlapping range updates in one pass instead of touching every point in every range.

The slow way first

The naive idea: for every trip, loop over every location from from to to and add its passengers there. Then scan the locations and check none exceeds capacity. With many long, overlapping trips this is O(trips × distance) — you re-touch the same stretch of road again and again.

The question to ask: do I really need to update every location inside a range? No. A passenger count only changes at the two endpoints — where people board and where they leave. Everywhere in between, the count is unchanged.

The idea: stamp the endpoints, sweep once

Keep a difference array diff indexed by location. For a trip [p, from, to], record only two events: diff[from] += p (p people board here) and diff[to] -= p (p people leave here). After all trips are stamped, walk left to right keeping a running total — the prefix sum. That running total is exactly how many passengers are in the car at each point. If it ever exceeds capacity, return false.

The key insight: a range update becomes two point updates plus one sweep. Stamping is O(trips), the sweep is O(range), and they never multiply together.

Walk through it

Step through the animation. First we stamp each trip: +2 lands at location 1 and -2 at location 5; then +3 at 3 and -3 at 6. Then the i pointer sweeps left to right, accumulating load. At location 3 the load jumps to 2 + 3 = 5, which beats the capacity of 4 — so we stop and return false.

Pseudocode

diff = array of zeros, one slot per location
for each trip [p, from, to]:
    diff[from] += p          # p passengers board at "from"
    diff[to]   -= p          # p passengers leave at "to"
load = 0
for change in diff:          # sweep the prefix sum
    load += change
    if load > capacity:
        return false         # too many people in the car here
return true

The Python solution

def car_pooling(trips, capacity):
    diff = [0] * 1001
    for p, frm, to in trips:
        diff[frm] += p
        diff[to] -= p
    load = 0
    for change in diff:
        load += change
        if load > capacity:
            return False
    return True

• diff = [0] * 1001 — the constraints cap locations at 1000, so one slot per location covers the whole road.
• For each trip we do two point updates: +p where passengers board, -p where they leave.
• load is the running prefix sum — the number of passengers in the car at the current location.
• Lines 9-10 are the check: the moment load exceeds capacity, the trip is impossible, so we return False early.
• If the sweep finishes without ever overflowing, every point was within capacity, so we return True.

Complexity

Because locations are bounded by 1000, the sweep is effectively constant work, so this runs in O(n) for n trips. We trade a fixed-size array for turning every range update into two cheap point updates.

When this pattern shows up

Practice