Car Pooling

Problem#

A car has capacity seats. trips[i] = [passengers, from, to] means passengers people get on at from and off at to. Return true iff capacity is never exceeded.

Examples#

trips = [[2,1,5],[3,3,7]], capacity = 4 → false
trips = [[2,1,5],[3,3,7]], capacity = 5 → true

Constraints#

1 <= trips.length <= 1000, 0 <= from < to <= 1000.

Approach#

Difference array on locations: delta[from] += passengers, delta[to] -= passengers. Sweep and accumulate; any prefix sum > capacity is a fail.

Solution#

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int delta[1001] = {0};
        for (auto& t : trips) {
            delta[t[1]] += t[0];
            delta[t[2]] -= t[0];
        }
        int cur = 0;
        for (int x : delta) {
            cur += x;
            if (cur > capacity) return false;
        }
        return true;
    }
};

func carPooling(trips [][]int, capacity int) bool {
    var delta [1001]int
    for _, t := range trips {
        delta[t[1]] += t[0]
        delta[t[2]] -= t[0]
    }
    cur := 0
    for _, x := range delta {
        cur += x
        if cur > capacity {
            return false
        }
    }
    return true
}

from typing import List

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        delta = [0] * 1001
        for passengers, frm, to in trips:
            delta[frm] += passengers
            delta[to] -= passengers
        cur = 0
        for x in delta:
            cur += x
            if cur > capacity:
                return False
        return True

var carPooling = function(trips, capacity) {
    const delta = new Array(1001).fill(0);
    for (const [passengers, frm, to] of trips) {
        delta[frm] += passengers;
        delta[to] -= passengers;
    }
    let cur = 0;
    for (const x of delta) {
        cur += x;
        if (cur > capacity) return false;
    }
    return true;
};

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] delta = new int[1001];
        for (int[] t : trips) {
            delta[t[1]] += t[0];
            delta[t[2]] -= t[0];
        }
        int cur = 0;
        for (int x : delta) {
            cur += x;
            if (cur > capacity) return false;
        }
        return true;
    }
}

function carPooling(trips: number[][], capacity: number): boolean {
    const delta: number[] = new Array(1001).fill(0);
    for (const [passengers, frm, to] of trips) {
        delta[frm] += passengers;
        delta[to] -= passengers;
    }
    let cur = 0;
    for (const x of delta) {
        cur += x;
        if (cur > capacity) return false;
    }
    return true;
}

Editorial#

Difference arrays convert “add X to range [l, r)” from O(r - l) to O(1) per operation, with a single O(L) sweep at the end. Note delta[t[2]] -= passengers (passengers leave exactly at the destination — the trip is [from, to) in this problem’s semantics, so they shouldn’t count at index to).

Complexity#

Time: O(n + L).
Space: O(L).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#