Car Pooling

How it works

Instead of sorting events, we can use an array where each index represents a location on the route. We record passenger changes at each location: add passengers at pickup points and subtract at drop-off points. A single pass through this array gives us the passenger count at each location.

Steps

1. Find the range of locations (leftmost pickup to rightmost drop-off).
2. Create an array of size (range + 1) initialized to zero.
3. For each trip, add passengers at the pickup index and subtract at the drop-off index.
4. Iterate through the array, accumulating the passenger count.
5. If the count ever exceeds capacity, return false. Otherwise, return true.

Complexity

• Time complexity: O(n + N)
• Space complexity: O(N)

Where n is the size of the array trips and N is the difference between the rightmost location and the leftmost location.

Things to watch for

Not Processing Drop-offs Before Pickups at Same Location

When a passenger is dropped off and another is picked up at the same location, the drop-off must happen first. Failing to sort events so that drop-offs (negative values) come before pickups at the same location causes false capacity violations.

Checking Passengers Still in Car at Drop-off Location

Passengers are dropped off at the end location and are not in the car during that location. A common mistake is including passengers who should have already exited, leading to overcounting.

Off-by-One Error in Difference Array Index

When using a difference array, failing to account for the offset between actual locations and array indices causes incorrect passenger counts. This is especially problematic when locations do not start at zero.

from typing import List

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        L, R = float("inf"), float("-inf")
        for _, start, end in trips:
            L = min(L, start)
            R = max(R, end)

        N = R - L + 1
        passChange = [0] * (N + 1)
        for passengers, start, end in trips:
            passChange[start - L] += passengers
            passChange[end - L] -= passengers

        curPass = 0
        for change in passChange:
            curPass += change
            if curPass > capacity:
                return False

        return True

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int L = INT_MAX, R = INT_MIN;
        for (const auto& trip : trips) {
            L = min(L, trip[1]);
            R = max(R, trip[2]);
        }

        int N = R - L + 1;
        vector<int> passChange(N + 1, 0);
        for (const auto& trip : trips) {
            passChange[trip[1] - L] += trip[0];
            passChange[trip[2] - L] -= trip[0];
        }

        int curPass = 0;
        for (int change : passChange) {
            curPass += change;
            if (curPass > capacity) {
                return false;
            }
        }

        return true;
    }
};