# LeetCode 853: Car Fleet

## Problem Restatement

There are `n` cars driving toward the same destination.

The destination is at position `target`.

For each car:

| Data | Meaning |
|---|---|
| `position[i]` | Starting position of car `i` |
| `speed[i]` | Speed of car `i` |

A car cannot pass another car ahead of it.

If a faster car catches up to a slower car before the destination, they become one fleet. The faster car slows down and follows the slower car.

A single car also counts as one fleet.

If a car catches a fleet exactly at the destination, it still counts as part of that fleet.

Return the number of car fleets that arrive at the destination.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `target`, the destination position |
| Input | `position`, the starting positions of the cars |
| Input | `speed`, the speeds of the cars |
| Output | The number of car fleets that arrive at `target` |

Function shape:

```python
class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        ...
```

## Examples

Example 1:

```python
target = 12
position = [10, 8, 0, 5, 3]
speed = [2, 4, 1, 1, 3]
```

Compute how long each car needs to reach the target:

| Position | Speed | Time to target |
|---|---|---|
| `10` | `2` | `(12 - 10) / 2 = 1` |
| `8` | `4` | `(12 - 8) / 4 = 1` |
| `0` | `1` | `(12 - 0) / 1 = 12` |
| `5` | `1` | `(12 - 5) / 1 = 7` |
| `3` | `3` | `(12 - 3) / 3 = 3` |

Sort cars from closest to the target to farthest from the target:

| Position | Time |
|---|---|
| `10` | `1` |
| `8` | `1` |
| `5` | `7` |
| `3` | `3` |
| `0` | `12` |

The car at position `10` forms a fleet with arrival time `1`.

The car at position `8` also has time `1`, so it catches the first car exactly at the target. They are one fleet.

The car at position `5` takes time `7`, so it cannot catch the fleet ahead. It forms a new fleet.

The car at position `3` takes time `3`, so it catches the fleet ahead whose arrival time is `7`. It joins that fleet.

The car at position `0` takes time `12`, so it cannot catch the fleet ahead. It forms a new fleet.

So the answer is:

```python
3
```

Example 2:

```python
target = 10
position = [3]
speed = [3]
```

There is only one car, so there is one fleet.

```python
1
```

Example 3:

```python
target = 100
position = [0, 2, 4]
speed = [4, 2, 1]
```

Times to target:

| Position | Speed | Time |
|---|---|---|
| `4` | `1` | `96` |
| `2` | `2` | `49` |
| `0` | `4` | `25` |

The cars behind are faster and will catch the slower car ahead. They all become one fleet.

```python
1
```

## First Thought: Simulate the Cars

One direct idea is to simulate the movement of every car over time.

At each moment, we could update every car's position and merge cars when they meet.

This is not a good approach.

The cars move continuously, not in fixed integer steps. Choosing a time step can make the simulation inaccurate. A very small time step would also be too slow.

We need a mathematical way to know whether cars merge.

## Key Insight

The important value for each car is its time to reach the target if it drives alone:

```python
time = (target - position) / speed
```

Cars closer to the target affect cars behind them.

So we sort cars by position from closest to the target to farthest from the target.

Then we process cars in that order.

When we look at a car behind a fleet:

- If its arrival time is less than or equal to the fleet ahead, it catches that fleet.
- If its arrival time is greater, it cannot catch the fleet ahead, so it forms a new fleet.

Why?

A car behind can only catch a car or fleet ahead if it would arrive no later than that car or fleet when driving alone.

If it would arrive later, it is too slow to catch up before the target.

## Algorithm

Pair every car's position with its speed.

```python
cars = list(zip(position, speed))
```

Sort cars by position in descending order.

```python
cars.sort(reverse=True)
```

This lets us process cars from closest to the target to farthest.

Maintain:

```python
fleets = 0
slowest_time_ahead = 0
```

For each car:

1. Compute its time to target.
2. If this time is greater than `slowest_time_ahead`, it cannot catch the fleet ahead.
3. Count it as a new fleet.
4. Update `slowest_time_ahead`.

If the time is less than or equal to `slowest_time_ahead`, the car joins the fleet ahead, so we do not increase the count.

## Correctness

After sorting by position descending, every car we process is behind all cars already processed.

The variable `slowest_time_ahead` stores the arrival time of the fleet directly relevant to the current car. It is the time the current car must beat or match to catch the fleet ahead.

If the current car's time is less than or equal to `slowest_time_ahead`, then it would reach the destination no later than the fleet ahead if it drove alone. Since it starts behind that fleet, it must catch the fleet before or at the target. Therefore, it belongs to the same fleet.

If the current car's time is greater than `slowest_time_ahead`, then even driving alone it would arrive later than the fleet ahead. It cannot catch that fleet before the target. Therefore, it forms a new fleet.

The algorithm counts exactly one fleet each time a car cannot catch the fleet ahead. Every other car merges into an existing fleet. Therefore, the returned count is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Sorting the cars dominates the runtime |
| Space | `O(n)` | We store the paired cars |

The scan after sorting takes `O(n)` time.

## Implementation

```python
class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)

        fleets = 0
        slowest_time_ahead = 0

        for pos, spd in cars:
            time = (target - pos) / spd

            if time > slowest_time_ahead:
                fleets += 1
                slowest_time_ahead = time

        return fleets
```

## Code Explanation

We first pair positions and speeds:

```python
cars = sorted(zip(position, speed), reverse=True)
```

Sorting in reverse order puts cars closer to the target first.

For example:

```python
position = [10, 8, 0, 5, 3]
```

becomes:

```python
[10, 8, 5, 3, 0]
```

Then we keep two values:

```python
fleets = 0
slowest_time_ahead = 0
```

`fleets` counts how many separate fleets we have found.

`slowest_time_ahead` stores the arrival time of the last fleet ahead.

For every car:

```python
time = (target - pos) / spd
```

If this car needs more time than the fleet ahead:

```python
if time > slowest_time_ahead:
```

then it cannot catch that fleet. So it becomes a new fleet:

```python
fleets += 1
slowest_time_ahead = time
```

If `time <= slowest_time_ahead`, the car catches the fleet ahead, so we do nothing.

This also handles the case where a car catches a fleet exactly at the destination. Equal time means same fleet.

## Testing

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

    assert s.carFleet(
        12,
        [10, 8, 0, 5, 3],
        [2, 4, 1, 1, 3],
    ) == 3

    assert s.carFleet(
        10,
        [3],
        [3],
    ) == 1

    assert s.carFleet(
        100,
        [0, 2, 4],
        [4, 2, 1],
    ) == 1

    assert s.carFleet(
        10,
        [1, 4],
        [3, 2],
    ) == 1

    assert s.carFleet(
        10,
        [4, 1, 0, 7],
        [2, 2, 1, 1],
    ) == 3

    print("all tests passed")

test_car_fleet()
```

Test meaning:

| Test | Why |
|---|---|
| Standard multi-car case | Checks multiple merges and separate fleets |
| One car | Minimum non-empty input |
| All cars merge | Checks faster cars behind slower cars |
| Catch exactly at destination | Equal arrival time should count as one fleet |
| Mixed case | Checks both merge and non-merge behavior |