Problem Description

The Car Pooling problem requires you to determine if a car with a given number of seats (capacity) can successfully pick up and drop off all passengers for a series of trips. Each trip is represented as [numPassengers, from, to], meaning numPassengers must be picked up at location from and dropped off at location to (with from < to).

• You must not exceed the car's capacity at any point.
• Passengers must be picked up and dropped off at the given locations, and cannot be dropped off earlier or picked up later.
• Your function should return true if all trips can be completed without exceeding capacity, or false otherwise.
• Each trip is independent, but they may overlap (i.e. multiple passengers can be in the car at the same time).

Thought Process

At first glance, you might consider simulating each trip one by one, keeping track of passengers in the car at every location. However, this would be inefficient if the locations range is large (e.g., up to 1000), and checking every possible location for every trip would be slow.

Instead, we can notice that the only times the number of passengers changes are at pickup (from) and drop-off (to) locations. This leads to a more efficient approach: track the net change in passengers at each location, and then simulate the journey in order, updating the car's occupancy as we go.

This is similar to the "sweep line" or "difference array" technique, where we only record changes at specific points and then process them in order.

Solution Approach

• Step 1: For each trip, record the number of passengers picked up at from (add) and dropped off at to (subtract) using a difference array or a hash map.
• Step 2: Sort all unique locations where a pickup or drop-off occurs.
• Step 3: Iterate through the locations in order, updating the current number of passengers in the car by applying the net changes at each location.
• Step 4: At each location, check if the current number of passengers exceeds capacity. If it does, return false.
• Step 5: If you complete the loop without exceeding capacity, return true.

We use a map or array because lookups and updates are O(1), and sorting the keys is efficient since the number of unique locations is limited.

Example Walkthrough

Input: trips = [[2,1,5],[3,3,7]], capacity = 4

• Trip 1: 2 passengers from 1 to 5
• Trip 2: 3 passengers from 3 to 7

1. At location 1: +2 passengers (total: 2)
2. At location 3: +3 passengers (total: 5)
3. At location 5: -2 passengers (total: 3)
4. At location 7: -3 passengers (total: 0)

At location 3, we have 5 passengers, which exceeds the capacity of 4. Therefore, the function returns false.

Code Implementation

class Solution:
    def carPooling(self, trips, capacity):
        changes = [0] * 1001  # locations go up to 1000
        for num, start, end in trips:
            changes[start] += num
            changes[end] -= num
        curr = 0
        for passengers in changes:
            curr += passengers
            if curr > capacity:
                return False
        return True
      

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int changes[1001] = {0};
        for (const auto& trip : trips) {
            changes[trip[1]] += trip[0];
            changes[trip[2]] -= trip[0];
        }
        int curr = 0;
        for (int i = 0; i <= 1000; ++i) {
            curr += changes[i];
            if (curr > capacity) return false;
        }
        return true;
    }
};
      

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] changes = new int[1001];
        for (int[] trip : trips) {
            changes[trip[1]] += trip[0];
            changes[trip[2]] -= trip[0];
        }
        int curr = 0;
        for (int i = 0; i <= 1000; i++) {
            curr += changes[i];
            if (curr > capacity) return false;
        }
        return true;
    }
}
      

var carPooling = function(trips, capacity) {
    const changes = Array(1001).fill(0);
    for (const [num, start, end] of trips) {
        changes[start] += num;
        changes[end] -= num;
    }
    let curr = 0;
    for (let i = 0; i <= 1000; i++) {
        curr += changes[i];
        if (curr > capacity) return false;
    }
    return true;
};
      

Time and Space Complexity

• Brute-force approach: For each trip, simulate every location between from and to, which is O(n * maxLocation), where n is the number of trips and maxLocation is the largest location value. This is inefficient for large inputs.
• Optimized approach: We only process two events per trip (pickup and drop-off), and then iterate through all possible locations once. This is O(n + maxLocation), which is efficient since maxLocation is at most 1000.
• Space complexity: Both approaches use O(maxLocation) space for the array of changes.

Summary

The Car Pooling problem is elegantly solved using the difference array (or sweep line) technique. By only recording changes at pick-up and drop-off points, we avoid unnecessary simulation and achieve an efficient solution. The key insight is to recognize that only the locations where passengers get in or out matter, making the solution both fast and easy to implement.