Car Pooling

Problem

A car with capacity seats travels one direction. Each trip: (numPassengers, start, end). Return true if car can take all trips.

Key insight: Bucket approach — array of size 1001 (max location). Add at start, subtract at end. Running sum must never exceed capacity.

Solutions

// C — bucket approach
bool carPooling(int** trips, int n, int capacity) {
    int stops[1001] = {0};
    for (int i = 0; i < n; i++) {
        stops[trips[i][1]] += trips[i][0];
        stops[trips[i][2]] -= trips[i][0];
    }
    int cur = 0;
    for (int i = 0; i <= 1000; i++) {
        cur += stops[i];
        if (cur > capacity) return false;
    }
    return true;
}

// C++
bool carPooling(vector<vector<int>>& trips, int capacity) {
    vector<int> stops(1001, 0);
    for (auto& t : trips) { stops[t[1]] += t[0]; stops[t[2]] -= t[0]; }
    int cur = 0;
    for (int s : stops) { cur += s; if (cur > capacity) return false; }
    return true;
}

// Java
public boolean carPooling(int[][] trips, int capacity) {
    int[] stops = new int[1001];
    for (int[] t : trips) { stops[t[1]] += t[0]; stops[t[2]] -= t[0]; }
    int cur = 0;
    for (int s : stops) { cur += s; if (cur > capacity) return false; }
    return true;
}

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

# Python
def carPooling(trips, capacity):
    stops = [0] * 1001
    for passengers, start, end in trips:
        stops[start] += passengers
        stops[end] -= passengers
    cur = 0
    for s in stops:
        cur += s
        if cur > capacity:
            return False
    return True

Complexity

Time: O(n + 1001) = O(n)
Space: O(1001) = O(1)

Key Insight

Difference array technique: mark +passengers at start, -passengers at end. Running prefix sum = current occupancy at each location.