> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Car Pooling Python Solution with Tests

> Tested Python solution for LeetCode 1094 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 1094, Medium. Topics: Array, Simulation, Prefix Sum. [View on LeetCode](https://leetcode.com/problems/car-pooling/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1094   # by problem number
lcpy gen -s car_pooling   # by problem name
```

## 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.

### Examples

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

```
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 <= 10^5`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/car_pooling/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/car_pooling/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n + L) where n = len(trips), L = max location (1001)
    # Space: O(L) for the difference array
    def car_pooling(self, trips: list[list[int]], capacity: int) -> bool:
        # Difference array: pickups add passengers at `from`, drop-offs remove at `to`.
        delta: list[int] = [0] * 1001
        for passengers, start, end in trips:
            delta[start] += passengers
            delta[end] -= passengers

        current = 0
        for load in delta:
            current += load
            if current > capacity:
                return False

        return True
```

## Complexity

| Time                                                   | Space                         |
| ------------------------------------------------------ | ----------------------------- |
| O(n + L) where n = len(trips), L = max location (1001) | O(L) for the difference array |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).