1094. Car Pooling

This problem asks whether a car with a given capacity can accommodate all passengers from a list of trips. Each trip specifies the number of passengers, the pickup location, and the drop-off location. The car only moves east.

Solution: Difference Array

The most efficient solution uses a difference array. This approach avoids iterating through all possible locations, improving efficiency.

Algorithm:

1. Initialization: Create a difference array d of size M + 1, where M is the maximum drop-off location. Initialize all elements to 0.

2. Processing Trips: Iterate through each trip [numPassengers, from, to]:

   • Add numPassengers to d[from] (passengers get on).
   • Subtract numPassengers from d[to] (passengers get off).

3. Prefix Sum Calculation: Calculate the prefix sum of the difference array. This represents the number of passengers in the car at each location.

4. Capacity Check: Iterate through the prefix sum. If at any point the prefix sum exceeds capacity, return false. Otherwise, return true.

Time Complexity: O(n + M), where n is the number of trips and M is the maximum drop-off location. The dominant operation is iterating through the trips and calculating the prefix sum. Since M is at most 1000 in the problem constraints, this simplifies to O(n) for practical purposes.

Space Complexity: O(M), the space used for the difference array. Again, since M is bounded, this is effectively constant space.

Code Implementation (Python):

from itertools import accumulate
 
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        mx = max(e[2] for e in trips)  # Find maximum drop-off location
        d = [0] * (mx + 1)             # Initialize difference array
 
        for x, f, t in trips:          # Process each trip
            d[f] += x                  # Add passengers at pickup
            d[t] -= x                  # Subtract passengers at drop-off
 
        prefix_sums = list(accumulate(d))  # Calculate prefix sums
 
        return all(s <= capacity for s in prefix_sums) # Check capacity at each location
 

Code Implementation (Other Languages): The core logic remains the same across languages; the primary differences are in syntax and library functions for array creation and prefix sum calculation.

Java:

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

C++:

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

Other languages (Javascript, TypeScript, Go, Rust, C#) would follow similar patterns, adapting the syntax for array/vector creation and manipulation accordingly. The fundamental algorithmic approach using the difference array remains consistent.