Car Pooling

Share

Given trips where trips[i]=[numPassengers, from, to] and capacity, return true if you can pick up and drop off all passengers without exceeding vehicle capacity at any point.

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

Solution Approach

Use a difference array (event-based). At each pickup location add passengers, at dropoff subtract. Scan from left and check if passengers ever exceed capacity.

  • Create a diff[] array of size 1001 (max stop value).
  • For each trip: diff[from] += num; diff[to] -= num.
  • Scan diff[]: if running sum > capacity at any point, return false.
Java
class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] diff = new int[1001];
        for (int[] t : trips) { diff[t[1]] += t[0]; diff[t[2]] -= t[0]; }
        int cur = 0;
        for (int d : diff) {
            cur += d;
            if (cur > capacity) return false;
        }
        return true;
    }
}
  • Time Complexity: O(N + M) where M=1001
  • Space Complexity: O(M)