Car Pooling — Difference Array and Event Sweep for Capacity Checking

Problem Statement#

There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).

You are given the integer capacity and an array trips where trips[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the passengers must be picked up at location fromi and dropped off at location toi. The locations are given as the number of kilometers due east from the car's initial location.

Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.

Constraints:

• 1 <= trips.length <= 1000
• 1 <= numPassengersi <= 100
• 0 <= fromi < toi <= 1000
• 1 <= capacity <= 10^5

Examples:

Input:  trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
 
Explanation:
  At location 3: 2 (from trip 1) + 3 (from trip 2) = 5 passengers > capacity 4.

Input:  trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true

Input:  trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true

Why This Problem Matters#

Car Pooling is an excellent interval problem that tests whether you know the difference array technique — a powerful tool for handling range-update queries in O(1) per update and O(n) for a final prefix-sum scan. Amazon, Facebook, and Google use it in online assessments and phone screens to check knowledge of this important optimization.

The problem also has a clean event-based heap solution: process events (passenger pickup and dropoff) in chronological order using a min-heap of (time, passenger_delta) events. This is the same pattern as "Meeting Rooms II" but for capacity checking rather than room counting.

The difference array approach, however, is the optimal solution for this specific problem. Because locations are bounded by 1000, the entire solution runs in O(n + 1000) = O(n) time with O(1000) = O(1) space — faster than any heap-based approach.

Understanding both approaches is valuable because:

1. The difference array is optimal but requires bounded locations.
2. The heap/event approach is more general and works when locations are arbitrary integers up to 10^9.

This problem also models real-world logistics: Uber/Lyft pool scheduling, package delivery capacity planning, and elevator capacity management all follow the same "add at pickup, subtract at dropoff" pattern.

The Core Insight#

Difference array approach: Create an array stops[0..1000]. For each trip with n passengers picked up at from and dropped at to:

• stops[from] += n (passengers board)
• stops[to] -= n (passengers exit)

Then compute the prefix sum of stops. The prefix sum at any position equals the current occupancy. If any prefix sum exceeds capacity, return false.

This works because the car only moves east — from < to is guaranteed. Passengers are in the car for the interval [from, to).

Why stops[to] -= n not stops[to-1] -= n? Passengers exit at location to, so they're not in the car at to. The prefix sum from 0 to to-1 is the occupancy just before dropoff, and the sum at to decrements by n.

trips = [[2,1,5],[3,3,7]], capacity = 4
 
stops[1] += 2 → stops[1] = 2
stops[5] -= 2 → stops[5] = -2
stops[3] += 3 → stops[3] = 3
stops[7] -= 3 → stops[7] = -3
 
Prefix sum: [0,2,2,5,5,3,3,0,...]
                          ↑
                    5 > 4 → false

Visual Dry Run#

Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11

stops array (only non-zero indices):

• stops[2] = 3, stops[3] = 8, stops[7] = 0 (−3+3=0), stops[9] = −11

Prefix sum scan:

• pos 0-1: 0
• pos 2: 3
• pos 3: 3+8 = 11
• pos 4-6: 11
• pos 7: 11+0 = 11
• pos 8: 11 (unchanged)
• pos 9: 11−11 = 0

Max occupancy = 11 = capacity. Return true. ✓

Solution (Optimal)#

def carPooling(trips: list[list[int]], capacity: int) -> bool:
    # Difference array: bounded by max location (1000 + 1 for safety)
    stops = [0] * 1001
 
    for passengers, from_loc, to_loc in trips:
        stops[from_loc] += passengers
        stops[to_loc] -= passengers    # passengers exit AT to_loc
 
    # Prefix sum scan: check if occupancy ever exceeds capacity
    current = 0
    for s in stops:
        current += s
        if current > capacity:
            return False
 
    return True
 
# Event-based approach (works for unbounded locations)
import heapq
 
def carPoolingEvents(trips: list[list[int]], capacity: int) -> bool:
    # Create events: (location, delta) where delta = +passengers or -passengers
    events = []
    for passengers, from_loc, to_loc in trips:
        events.append((from_loc, passengers))    # pick up
        events.append((to_loc, -passengers))     # drop off
 
    # Sort by location; dropoffs before pickups at same location
    events.sort(key=lambda x: (x[0], x[1]))
 
    current = 0
    for _, delta in events:
        current += delta
        if current > capacity:
            return False
 
    return True

function carPooling(trips, capacity) {
    const stops = new Array(1001).fill(0);
 
    for (const [n, from, to] of trips) {
        stops[from] += n;
        stops[to] -= n;
    }
 
    let current = 0;
    for (const s of stops) {
        current += s;
        if (current > capacity) return false;
    }
 
    return true;
}

Complexity Analysis:

The difference array approach is optimal for this problem because location values are bounded by 1000. The O(1001) space is effectively constant.

Common Mistakes#

• Using stops[to - 1] -= n instead of stops[to] -= n. Passengers exit at location to. If you decrement at to-1, you remove them before they should exit, giving incorrect intermediate occupancies.
• Not handling the case where from == to. If from == to, a trip with 0 distance contributes 0 passengers (they board and exit at the same location). The difference array handles this correctly: stops[x] += n; stops[x] -= n nets to 0.
• Overflow in the prefix sum. With capacity up to 10^5 and numPassengers up to 100 over 1000 trips, total passengers can reach 10^5. The prefix sum can reach 10^5 but not exceed int range.
• Wrong event sort key for the event approach. At the same location, dropoffs should happen before pickups. Sort by (location, delta) where delta is negative for dropoffs — this puts dropoffs first (negative numbers sort before positive).
• Not checking the entire path. You must check capacity at every stop from 0 to 1000, not just at pickup and dropoff points. The prefix sum naturally handles intermediate points.

Follow-up Questions#

• What if locations can be up to 10^9? The difference array approach needs 10^9 entries — infeasible. Use the event-sort approach instead: O(n log n) time, O(n) space.
• What if the car can travel both east and west? The problem structure changes fundamentally. You'd need to track which passengers are on board at each location in both directions.
• What if you want the maximum occupancy (not just feasibility)? Compute the prefix sum and return its maximum value instead of comparing against capacity.
• What if you want to know which trips cause violations? Record which trips contribute to the exceeding occupancy during the prefix sum scan.
• How does this relate to "Meeting Rooms II"? Meeting Rooms II counts the peak simultaneous meetings (= rooms needed). Car Pooling checks if peak occupancy ever exceeds a limit. Both use the same event-sweep or difference array pattern.

Related Problems#

• 1094. Car Pooling — this problem.
• 253. Meeting Rooms II — count peak simultaneous meetings (same event pattern).
• 56. Merge Intervals — interval merging, prerequisite knowledge.
• 1109. Corporate Flight Bookings — direct application of difference array technique.
• 370. Range Addition — classic difference array problem (premium LeetCode).
• 731. My Calendar II — count overlapping intervals up to a limit, similar feasibility check.

Key Takeaways#

• Difference array is optimal for bounded locations: stops[from] += n, stops[to] -= n, then scan prefix sum
• Passengers exit AT to_loc, not at to_loc - 1 — use stops[to] -= n, not stops[to-1] -= n
• If any prefix sum exceeds capacity, return false — the car was overloaded at that location
• Difference array is O(n + 1001) = O(n) time and O(1001) = O(1) space — optimal for this problem
• Event-based approach (sort by location, process pickup +n and dropoff -n events) works for unbounded locations
• Sort events so dropoffs happen before pickups at the same location — use (location, delta) as sort key
• This add-at-start, subtract-at-end difference array pattern is the foundation for LC 1109 and LC 370