Car Pooling: Difference Arrays Meet Interval Events

"Car Pooling" shows up again and again in Uber, Amazon, Google phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Merge Intervals pattern quickly and code it cleanly. Part 9 of 11 in the Merge Intervals arc.

The Problem

Given trips as [passengers, pickup, dropoff] and a vehicle capacity, return whether all trips can be served by one car driving east only. Passengers occupy the half-open range pickup to dropoff. This is Meeting Rooms II with weights — concurrent load instead of concurrent count.

Input:  trips = [[2, 1, 5], [3, 3, 7]], capacity = 4
Output: False
Between kilometers 3 and 5 the car holds 5 passengers.

Recognizing the Merge Intervals Pattern

Interval problems — scheduling, calendars, resource booking — almost all reduce to one move: sort by start (or end), then sweep once while comparing each interval against a running boundary. Overlap exists when the next start is at most the current end. Sort plus linear sweep, O(n log n), is the backbone of the entire family.

Weighted intervals with a max-load question is the event-sweep member of the family: +p at pickup, −p at dropoff, running sum against capacity. Bounded coordinates (stops up to 1000) additionally allow a difference array — no sort at all.

The Approach

Difference array version: diff[pickup] += p, diff[dropoff] -= p, then prefix-sum and compare each running load against capacity. Dropoff frees seats exactly at its stop because the range is half-open — the +/− placement encodes that convention.

If coordinates were unbounded, sort the 2n events instead (ends before starts at ties) — same running sum, O(n log n). Offering both with the boundary condition handled is a complete answer.

Python Solution

def car_pooling(trips: list[list[int]], capacity: int) -> bool:
    """True if the running passenger load never exceeds capacity."""
    diff = [0] * 1001                     # stops are 0..1000
    for passengers, pickup, dropoff in trips:
        diff[pickup] += passengers
        diff[dropoff] -= passengers       # seats free exactly at dropoff
    load = 0
    for delta in diff:
        load += delta
        if load > capacity:
            return False
    return True

Complexity

• Time: O(n + K) — n trips plus a sweep over K = 1001 stops
• Space: O(K) — the difference array

Interview Tips and Follow-Ups

• Justify the half-open handling in one sentence — a dropoff and pickup at the same stop must not double-count, and the diff placement guarantees it.
• If the interviewer removes the coordinate bound, pivot to sorted events without missing a beat — that pivot is the real test.
• Difference arrays generalize to range-update problems (Corporate Flight Bookings is the same code) — name the family.

That wraps part 9 of the Merge Intervals arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.