# Car Pooling
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/car-pooling)
Canonical: https://scaleengineer.com/dsa/problems/car-pooling
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Lyft](https://scaleengineer.com/companies/lyft), [Zepto](https://scaleengineer.com/companies/zepto)
---
## Problem
There is a car with `capacity` empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).

You are given the integer `capacity` and an array `trips` where `trips[i] = [numPassengersi, fromi, toi]` indicates that the `ith` trip has `numPassengersi` passengers and the locations to pick them up and drop them off are `fromi` and `toi` respectively. The locations are given as the number of kilometers due east from the car's initial location.

Return `true` _if it is possible to pick up and drop off all passengers for all the given trips, or_ `false` _otherwise_.

**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

**Constraints:**

* `1 <= trips.length <= 1000`
* `trips[i].length == 3`
* `1 <= numPassengersi <= 100`
* `0 <= fromi < toi <= 1000`
* `1 <= capacity <= 105`

# Approaches
## Brute-Force Simulation
This approach directly simulates the car's journey kilometer by kilometer. It works by maintaining an array that represents every location on the route and calculating the total number of passengers present in the car at each of these locations. It's the most straightforward way to conceptualize the problem but also the least efficient.
**Time:** O(N * M), where N is the number of trips and M is the maximum possible location. For each of the N trips, we might iterate up to M locations. · **Space:** O(M), where M is the maximum possible location (1001 in this case). We need an array to store the passenger count for each location.
**Pros:** Very easy to understand and implement.; It's a direct translation of the problem statement into code.
**Cons:** Highly inefficient, especially if the range of locations or the number of trips is large.; The time complexity of O(N * M) can be too slow for stricter time limits.
### Explanation
We begin by creating an array, let's call it `passengerCount`, to represent the timeline of the car's trip. The size of this array will be 1001 to accommodate all possible locations from 0 to 1000, as per the problem constraints. Each index `i` in this array will store the total number of passengers in the car at kilometer `i`.

We then iterate through every trip provided. For a given trip `[numPassengers, from, to]`, we know that `numPassengers` are added to the car for the entire interval of locations from `from` up to (but not including) `to`. Therefore, we loop from `from` to `to - 1` and add `numPassengers` to the `passengerCount` at each of these locations.

After processing all the trips in this manner, the `passengerCount` array will accurately reflect the number of occupants at every point in the journey. The final step is to iterate through this `passengerCount` array and check if the passenger load at any location exceeded the car's `capacity`. If we find any such location, we immediately know the scenario is impossible and return `false`. If we complete the scan without any violations, it means all trips can be accommodated, and we return `true`.

```java
class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        // As per constraints, the maximum location is 1000.
        int[] passengerCount = new int[1001];

        // Add passengers for each trip to the locations they occupy.
        for (int[] trip : trips) {
            int numPassengers = trip[0];
            int from = trip[1];
            int to = trip[2];
            for (int i = from; i < to; i++) {
                passengerCount[i] += numPassengers;
            }
        }

        // Check if capacity is exceeded at any point.
        for (int count : passengerCount) {
            if (count > capacity) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
1. Create an integer array `passengerCount` of size 1001 (to cover locations 0 to 1000), initialized to all zeros.
2. Iterate through each `trip` in the `trips` array.
3. For each `trip = [num, from, to]`, start a nested loop that iterates from `i = from` to `to - 1`.
4. Inside the nested loop, increment `passengerCount[i]` by `num`.
5. After processing all trips and populating the `passengerCount` array, iterate through it from start to end.
6. If at any point an element `passengerCount[i]` is greater than `capacity`, it means the car is over capacity at that location. Return `false`.
7. If the final loop completes without finding any over-capacity situations, return `true`.

## Sorting Timeline Events
A more optimized approach is to recognize that the number of passengers in the car only changes at pickup and drop-off locations. We can model these as 'events' on a timeline. By creating a list of all such events and processing them in chronological order, we can efficiently track the passenger load.
**Time:** O(N log N), where N is the number of trips. The dominant operation is sorting the list of 2*N events. · **Space:** O(N), where N is the number of trips. We need to store 2*N events.
**Pros:** Much more efficient than brute-force, especially if the location range is sparse and large.; This approach is general and works well even if location values are not constrained to a small range.
**Cons:** The sorting step has a time complexity of O(N log N), which can be less efficient than a linear-time approach when the range of locations is small.; Requires more complex data structures (list of objects/arrays) and custom sorting logic compared to the Difference Array approach.
### Explanation
Instead of checking every kilometer, we focus only on the points where the passenger count changes. For each trip `[num, from, to]`, we can define two critical events: `num` passengers getting on at `from`, and `num` passengers getting off at `to`. We can represent these as a change in passenger count: `+num` at `from` and `-num` at `to`.

We first create a list containing all these `2*N` events (where N is the number of trips). Then, we sort these events based on their location. A crucial detail for sorting is handling events at the same location: we must process drop-offs (`-num`) before pickups (`+num`). This correctly models passengers leaving the car and freeing up space before new passengers board at the same spot. This can be achieved with a secondary sort key on the passenger change value.

After sorting, we iterate through the event list, maintaining a running count of `currentPassengers`. For each event, we apply the passenger change and then check if the new `currentPassengers` count exceeds the car's `capacity`. If it ever does, we return `false`. If we successfully process all events, it means the capacity was never violated, and we can return `true`.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        List<int[]> events = new ArrayList<>();
        for (int[] trip : trips) {
            // Event: [location, change_in_passengers]
            events.add(new int[]{trip[1], trip[0]});  // Pickup event
            events.add(new int[]{trip[2], -trip[0]}); // Drop-off event
        }

        // Sort events: 1. by location, 2. by passenger change (drop-offs first)
        Collections.sort(events, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return a[1] - b[1];
            }
        });

        int currentPassengers = 0;
        for (int[] event : events) {
            currentPassengers += event[1];
            if (currentPassengers > capacity) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
1. Create a list to store timeline events. An event can be represented by an array or object, e.g., `[location, passenger_change]`.
2. Iterate through each `trip = [num, from, to]`.
3. For each trip, create two events: a pickup event `[from, num]` and a drop-off event `[to, -num]`. Add both to the list.
4. Sort the list of events. The primary sorting key is the `location`. For events at the same location, the secondary key is `passenger_change` (this ensures drop-offs are processed before pickups, freeing up space).
5. Initialize a variable `currentPassengers = 0`.
6. Iterate through the sorted list of events.
7. For each event, update `currentPassengers` by adding the `passenger_change`.
8. After each update, check if `currentPassengers > capacity`. If it is, return `false`.
9. If the loop completes without exceeding capacity, return `true`.

## Difference Array / Bucket Sort
This is the most efficient approach for the given problem constraints. It uses a difference array to record the net change in passengers at each location. By calculating a running sum (prefix sum) over this array, we can determine the actual passenger load at any point in linear time, avoiding any sorting.
**Time:** O(N + M), where N is the number of trips and M is the maximum location. It takes O(N) to populate the difference array and O(M) to compute the running sum. · **Space:** O(M), where M is the maximum possible location (1001). This is for the `locationChanges` array.
**Pros:** Extremely efficient with linear time complexity, making it the fastest solution for the given constraints.; Conceptually simple and avoids the overhead of sorting or complex data structures.
**Cons:** The space complexity is dependent on the maximum location value (`M`). This approach would be memory-inefficient if the locations could be very large (e.g., up to 10^9).
### Explanation
This technique, also known as bucket sort for its discrete mapping of events to locations, leverages the fact that all locations are within a fixed, small range [0, 1000].

We create an array, `locationChanges`, of size 1001. Instead of storing the absolute number of passengers, this array will store the *change* in the number of passengers at each location. For each trip `[num, from, to]`, we perform two simple operations: we add `num` at index `from` (since `num` passengers board here) and subtract `num` at index `to` (since `num` passengers alight here).

After iterating through all the trips, the `locationChanges` array contains the net effect of all pickups and drop-offs at every single location. For example, if `locationChanges[5]` is 3, it means that at location 5, the number of passengers in the car increases by a net of 3.

Finally, we can find the actual number of passengers at any point by iterating through the `locationChanges` array and keeping a running sum. We start with zero passengers. At each location `i`, we add `locationChanges[i]` to our current passenger count. This updated count is the number of people in the car from location `i` onwards (until the next change). After each update, we check if this count exceeds `capacity`. If it does, we return `false`. If we can scan through all locations without a violation, we return `true`.

```java
class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        // Constraints: 0 <= from < to <= 1000
        // Use a difference array to store the change in passengers at each location.
        int[] locationChanges = new int[1001];

        for (int[] trip : trips) {
            int numPassengers = trip[0];
            int from = trip[1];
            int to = trip[2];
            locationChanges[from] += numPassengers;
            locationChanges[to] -= numPassengers;
        }

        // Calculate the actual passenger load at each location by using a running sum.
        int currentPassengers = 0;
        for (int change : locationChanges) {
            currentPassengers += change;
            // Check if the capacity is exceeded at any point.
            if (currentPassengers > capacity) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
1. Create an integer array `locationChanges` of size 1001, initialized to all zeros. This array will store the net change of passengers at each location.
2. Iterate through each `trip = [num, from, to]`.
3. For each trip, add `num` to `locationChanges[from]` and subtract `num` from `locationChanges[to]`.
4. After processing all trips, initialize a variable `currentPassengers = 0`.
5. Iterate through the `locationChanges` array from the first to the last location (index 0 to 1000).
6. In each iteration, add the value `locationChanges[i]` to `currentPassengers`. This running sum represents the total passengers in the car at location `i`.
7. After updating, check if `currentPassengers` exceeds `capacity`. If it does, return `false`.
8. If the loop completes without any capacity violations, return `true`.

# Solutions
### CSharp

```csharp
public class Solution {
    public bool CarPooling(int[][] trips, int capacity) {
        int mx = trips.Max(x => x[2]);
        int[] d = new int[mx + 1];
        foreach(var trip in trips) {
            int x = trip[0], f = trip[1], t = trip[2];
            d[f] += x;
            d[t] -= x;
        }
        int s = 0;
        foreach(var x in d) {
            s += x;
            if (s > capacity) {
                return false;
            }
        }
        return true;
    }
}
```

### Java

```java
class Solution {
public
  boolean carPooling(int[][] trips, int capacity) {
    int[] d = new int[1001];
    for (var trip : trips) {
      int x = trip[0], f = trip[1], t = trip[2];
      d[f] += x;
      d[t] -= x;
    }
    int s = 0;
    for (int x : d) {
      s += x;
      if (s > capacity) {
        return false;
      }
    }
    return true;
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} trips * @param {number} capacity * @return {boolean} */ var carPooling =
  function (trips, capacity) {
    const mx = Math.max(...trips.map(([, , t]) => t));
    const d = Array(mx + 1).fill(0);
    for (const [x, f, t] of trips) {
      d[f] += x;
      d[t] -= x;
    }
    let s = 0;
    for (const x of d) {
      s += x;
      if (s > capacity) {
        return false;
      }
    }
    return true;
  };

```

### CPP

```cpp
class Solution {
public:
  bool carPooling(vector<vector<int>> &trips, int capacity) {
    int d[1001]{};
    for (auto &trip : trips) {
      int x = trip[0], f = trip[1], t = trip[2];
      d[f] += x;
      d[t] -= x;
    }
    int s = 0;
    for (int x : d) {
      s += x;
      if (s > capacity) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool: mx = max(e[2] for e in trips) d = [0] * (mx + 1) for x, f, t in trips: d[f] += x d[t] -= x return all(s <= capacity for s in accumulate(d))

```