> ## 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 Fleet Python Solution with Tests

> Tested Python solution for LeetCode 853 with 13 pytest cases. Generate a practice environment with lcpy.

LeetCode 853, Medium. Topics: Array, Stack, Sorting, Monotonic Stack. [View on LeetCode](https://leetcode.com/problems/car-fleet/description/).

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

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

## Problem

There are `n` cars at given miles away from the starting mile 0, traveling to reach the mile `target`.

You are given two integer arrays `position` and `speed`, both of length `n`, where `position[i]` is the starting mile of the `i<sup>th</sup>` car and `speed[i]` is the speed of the `i<sup>th</sup>` car in miles per hour.

A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car.

A **car fleet** is a single car or a group of cars driving next to each other. The speed of the car fleet is the **minimum** speed of any car in the fleet.

If a car catches up to a car fleet at the mile `target`, it will still be considered as part of the car fleet.

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

### Examples

```
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
- The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12. The fleet forms at target.
- The car starting at 0 (speed 1) does not catch up to any other car, so it is a fleet by itself.
- The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
```

```
Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation: There is only one car, hence there is only one fleet.
```

```
Input: target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
```

### Constraints

* n == position.length == speed.length
* 1 \<= n \<= 10\<sup>5\</sup>
* 0 \< target \<= 10\<sup>6\</sup>
* 0 \<= position\[i] \< target
* All the values of position are **unique**.
* 0 \< speed\[i] \<= 10\<sup>6\</sup>

## Solution

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

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def car_fleet(self, target: int, position: list[int], speed: list[int]) -> int:
        # Sort cars by position descending (closest to target first).
        cars = sorted(zip(position, speed, strict=False), reverse=True)
        fleets = 0
        slowest_arrival = 0.0
        for pos, spd in cars:
            arrival = (target - pos) / spd
            # A car forms a new fleet only if it arrives strictly later than
            # the fleet ahead of it; otherwise it catches up and merges.
            if arrival > slowest_arrival:
                fleets += 1
                slowest_arrival = arrival
        return fleets
```

## Complexity

| Time       | Space |
| ---------- | ----- |
| O(n log n) | O(n)  |

## Tags

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