Problem statement

A car with capacity seats drives east only. trips[i] = [numPassengers, from, to] picks up passengers at from and drops them at to.

Return true if all trips can be completed without ever exceeding capacity.

Example 1

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

Example 2

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

Constraints

• 1 <= trips.length <= 20
• 1 <= numPassengers <= 10
• 0 <= from < to <= 100
• 1 <= capacity <= 30

Hints for Car Pooling

1. Hint 1

   Difference array over positions: +num at pickup, -num at drop-off.

2. Hint 2

   The running prefix sum is the passenger count at each kilometer.

How to solve Car Pooling

You do not need to track individual trips — only how many passengers are aboard at each kilometre. A difference array records changes rather than totals: add passengers at the pickup point, subtract them at the drop-off. A single prefix sum then replays the occupancy along the route.

Approach

1. Make an array indexed by position, all zeros.
2. For each trip [num, from, to]: add num at index from, subtract num at index to.
3. Sweep positions left to right, maintaining a running sum — the passengers currently on board.
4. If the running sum ever exceeds capacity, return false.
5. Finishing the sweep means every point was within capacity.

Why it works

The running sum at position p counts exactly the trips with from <= p < to — each contributed +num at or before p and its matching -num only after — which is the set of passengers aboard at p. Since occupancy only changes at pickups and drop-offs, checking every index covers every moment. Subtracting at to rather than after it encodes that passengers leave before the car reaches the next segment, so a drop-off and a pickup at the same point do not conflict.

Complexity

• Time — O(n + maxPosition)
• Space — O(maxPosition)

Pitfalls

• Subtract at to, not to + 1. Passengers get out at to, so that point is already free for someone else.
• The trips arrive in arbitrary order; the difference array makes that irrelevant, which is the point of using one.
• Size the array to cover the largest to value — indexing past the end silently loses drop-offs.
• Exceeding capacity is > capacity; being exactly full is allowed.

Reference solution

Python

from typing import List

def carPooling(trips: List[List[int]], capacity: int) -> bool:
    diff = [0] * 102
    for num, frm, to in trips:
        diff[frm] += num
        diff[to] -= num
    cur = 0
    for d in diff:
        cur += d
        if cur > capacity:
            return False
    return True

Java

public static boolean carPooling(int[][] trips, int capacity) {
    int[] diff = new int[1002];
    for (int[] t : trips) {
        diff[t[1]] += t[0];
        diff[t[2]] -= t[0];
    }
    int onboard = 0;
    for (int p = 0; p < 1002; p++) {
        onboard += diff[p];
        if (onboard > capacity) return false;
    }
    return true;
}

C++

bool carPooling(vector<vector<int>>& trips, int capacity) {
    vector<int> diff(1002, 0);
    for (const auto& t : trips) {
        diff[t[1]] += t[0];
        diff[t[2]] -= t[0];
    }
    int onboard = 0;
    for (int p = 0; p < 1002; p++) {
        onboard += diff[p];
        if (onboard > capacity) return false;
    }
    return true;
}

JavaScript

var carPooling = function(trips, capacity) {
    const diff = new Array(102).fill(0);
    for (const t of trips) {
        diff[t[1]] += t[0];
        diff[t[2]] -= t[0];
    }
    let cur = 0;
    for (const d of diff) {
        cur += d;
        if (cur > capacity) return false;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium