Car Pooling

Share

A car with capacity seats picks up and drops off passengers at various stops. Return if all trips are possible.

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

Solution Approach

Use a difference array: add passengers at start, remove at end. Scan stops checking capacity.

  • Create stops array of size 1001
  • For each trip add passengers at from, subtract at to
  • Scan stops accumulating passengers
  • If any point exceeds capacity return false
Java
public boolean carPooling(int[][] trips, int capacity) {
    int[] stops = new int[1001];
    for (int[] trip : trips) {
        stops[trip[1]] += trip[0];
        stops[trip[2]] -= trip[0];
    }
    int passengers = 0;
    for (int count : stops) {
        passengers += count;
        if (passengers > capacity) return false;
    }
    return true;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)