# LeetCode 1094: Car Pooling

## Problem Restatement

We have a car with `capacity` seats.

We are given a list of trips: each trip `[numPassengers, from, to]` means `numPassengers` passengers board at `from` and alight at `to`.

We need to return `true` if it is possible to pick up all passengers without exceeding capacity at any point.

The official constraints state that `1 <= trips.length <= 1000`, `1 <= numPassengers <= 100`, and `0 <= from < to <= 1000`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `trips` list and integer `capacity` |
| Output | `true` if all trips can be completed without exceeding capacity |

Function shape:

```python
def carPooling(trips: list[list[int]], capacity: int) -> bool:
    ...
```

## Examples

Example 1:

```python
trips = [[2,1,5],[3,3,7]]
capacity = 4
```

At stop 1: 2 board → 2 passengers.

At stop 3: 3 board → 5 passengers. Exceeds capacity 4.

Answer:

```python
False
```

Example 2:

```python
trips = [[2,1,5],[3,3,7]]
capacity = 5
```

At stop 3: 5 passengers. Exactly at capacity.

Answer:

```python
True
```

## Key Insight

Use a difference array on the stops.

For each trip, add `numPassengers` at `from` and subtract `numPassengers` at `to`.

Compute the prefix sum and check if it ever exceeds `capacity`.

## Algorithm

1. Create a `stops` array of size `1001`.
2. For each trip, `stops[from] += numPassengers` and `stops[to] -= numPassengers`.
3. Compute the running sum. If it exceeds `capacity` at any point, return `False`.
4. Return `True`.

## Edge Cases

- Check the minimum input size allowed by the constraints.
- Verify duplicate values or tie cases if the input can contain them.
- Keep the return value aligned with the exact failure case in the statement.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n + S)` | `n` trips and `S = 1001` stops |
| Space | `O(S)` | Stops array |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
class Solution:
    def carPooling(self, trips: list[list[int]], capacity: int) -> bool:
        stops = [0] * 1001

        for num, frm, to in trips:
            stops[frm] += num
            stops[to] -= num

        current = 0
        for passengers in stops:
            current += passengers
            if current > capacity:
                return False

        return True
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.carPooling([[2,1,5],[3,3,7]], 4) == False
    assert s.carPooling([[2,1,5],[3,3,7]], 5) == True
    assert s.carPooling([[3,2,7],[3,7,9],[8,3,9]], 11) == True
    assert s.carPooling([[2,1,5],[3,5,7]], 3) == True

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| Overlap exceeds | `False` | 5 > 4 at some point |
| Exact capacity | `True` | Never exceeds 5 |
| Large capacity | `True` | Enough seats for all trips |
| Sequential trips | `True` | Passengers don't overlap |