# Car Fleet
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/car-fleet)
Canonical: https://scaleengineer.com/dsa/problems/car-fleet
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [Infosys](https://scaleengineer.com/companies/infosys), [Nutanix](https://scaleengineer.com/companies/nutanix), [Snap](https://scaleengineer.com/companies/snap), [GE Healthcare](https://scaleengineer.com/companies/ge-healthcare), [BharatPe](https://scaleengineer.com/companies/bharatpe)
---
## 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 array `position` and `speed`, both of length `n`, where `position[i]` is the starting mile of the `ith` car and `speed[i]` is the speed of the `ith` 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 car or 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.

**Example 1:**

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

**Example 2:**

**Input:** target = 10, position = \[3\], speed = \[3\]

**Output:** 1

**Explanation:**

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

**Example 3:**

**Input:** target = 100, position = \[0,2,4\], speed = \[4,2,1\]

**Output:** 1

**Explanation:**

* The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4\. The car starting at 4 (speed 1) travels to 5.
* Then, the fleet at 4 (speed 2) and the car at position 5 (speed 1) become one fleet, meeting each other at 6\. The fleet moves at speed 1 until it reaches `target`.

**Constraints:**

* `n == position.length == speed.length`
* `1 <= n <= 105`
* `0 < target <= 106`
* `0 <= position[i] < target`
* All the values of `position` are **unique**.
* `0 < speed[i] <= 106`

# Approaches
## Simulation after Sorting
This approach first sorts the cars based on their starting positions. Then, it simulates the process of merging fleets. It repeatedly scans through the cars from back to front (those further from the target to those closer), merging any car that would catch up to the one immediately in front of it. This simulation continues until no more merges can be made in a full pass, at which point the number of remaining cars (or fleets) is the answer.
**Time:** O(N^2) in the worst case. Sorting takes an initial O(N log N). The `while` loop can run up to N-1 times, and each pass involves an O(N) scan. This leads to a quadratic runtime. · **Space:** O(N) to store the list of `Car` objects for the simulation.
**Pros:** The logic is a direct simulation of the problem statement, which can be easier to conceptualize initially.
**Cons:** The time complexity is O(N^2) in the worst case, which is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error.; The implementation is more complex than the optimal solution, involving repeated modifications and iterations over a list.
### Explanation
The core idea is to directly simulate the physical process. After sorting the cars by position, we know their relative order. A car can only merge with the one directly ahead of it. We can use a dynamic list of cars and iterate through it. If we find a car `i` that will catch up to car `i+1` (meaning `time[i] <= time[i+1]`), we merge them by removing car `i`. Since this merge could cause the car previously at `i-1` to now be able to merge with the fleet at `i+1`, we must restart our scan. This process is repeated until a full scan of all cars results in no merges, indicating that the final fleet configuration has been reached.

```java
class Car {
    int position;
    double time;
    Car(int p, double t) {
        this.position = p;
        this.time = t;
    }
}

public int carFleet(int target, int[] position, int[] speed) {
    if (position.length <= 1) return position.length;
    List<Car> cars = new ArrayList<>();
    for (int i = 0; i < position.length; i++) {
        cars.add(new Car(position[i], (double)(target - position[i]) / speed[i]));
    }
    // Sort by position
    cars.sort(Comparator.comparingInt(a -> a.position));

    while (true) {
        boolean mergedInPass = false;
        for (int i = cars.size() - 2; i >= 0; i--) {
            // Car i is behind car i+1
            if (cars.get(i).time <= cars.get(i+1).time) {
                // Car i merges into the fleet of car i+1.
                // The new fleet's arrival time is that of car i+1.
                // We can just remove car i.
                cars.remove(i);
                mergedInPass = true;
                // Restart scan since the list has changed
                break; 
            }
        }
        if (!mergedInPass) {
            break; // No merges in a full pass, we are done.
        }
    }
    return cars.size();
}
```
### Algorithm
*   Create a list of custom `Car` objects, where each object stores a car's position and its calculated time to reach the target. The time is `(target - position) / speed`.
*   Sort this list of cars in ascending order of their positions.
*   Use a `while` loop that continues as long as merges occur in a pass.
*   Inside the loop, iterate through the cars from second-to-last to the first (`i` from `n-2` down to `0`).
*   If the arrival time of car `i` is less than or equal to the arrival time of car `i+1` (the one in front), it means car `i` merges into the fleet of `i+1`.
*   To handle the merge, remove car `i` from the list. Set a flag indicating a merge occurred and break the inner loop to restart the scan from the beginning of the modified list.
*   If the `while` loop completes a full pass over the cars without any merges, the fleets are stable. The loop terminates.
*   The final number of fleets is the size of the remaining list of cars.

## Optimal Greedy Approach with Sorting
This optimal approach hinges on a key insight: a car's behavior is only constrained by the cars ahead of it. By sorting the cars by position and then processing them from front-to-back (i.e., from closest to the target to furthest), we can make a simple greedy decision for each car. In a single pass, we can determine if a car forms a new fleet or merges with an existing one, leading to a highly efficient solution.
**Time:** O(N log N). The dominant operation is sorting the cars by position. The subsequent greedy scan is a single pass, taking O(N) time. · **Space:** O(N) to store the `Car` objects or pairs needed for sorting. If sorting can be done in-place on the input arrays (by pairing them logically), space could be O(1), but this is often not practical.
**Pros:** Optimal time complexity of O(N log N), which is very efficient and passes all constraints.; The logic is clean and requires only a single pass over the data after sorting.; Uses a constant amount of extra space besides the storage required for sorting.
**Cons:** The main performance bottleneck is the O(N log N) sorting step.; Requires the use of floating-point arithmetic for time calculations, which can have precision issues in some problems, though it's safe here.
### Explanation
The logic is that if car A is behind car B, they form a fleet only if car A can catch up to car B before or at the target. This is equivalent to saying that the time it would take car A to reach the target (if unobstructed) is less than or equal to the time it would take car B. 

By sorting the cars by position, we can iterate from the one closest to the target backwards. The car closest to the target is always the leader of a fleet. We record its arrival time. Then, for the next car behind it, we check if its arrival time is less than or equal to the leader's time. If it is, it merges. If it's greater, it's too slow and forms a new fleet, becoming the new 'leader' for the cars behind it. This process continues, maintaining the arrival time of the slowest fleet currently at the front. This is a form of monotonic stack logic, where the arrival times of the fleet leaders we identify will be strictly increasing.

```java
class Car {
    int position;
    int speed;
    Car(int p, int s) {
        this.position = p;
        this.speed = s;
    }
}

public int carFleet(int target, int[] position, int[] speed) {
    int n = position.length;
    if (n <= 1) {
        return n;
    }

    Car[] cars = new Car[n];
    for (int i = 0; i < n; i++) {
        cars[i] = new Car(position[i], speed[i]);
    }

    // Sort cars by position in ascending order
    Arrays.sort(cars, (a, b) -> Integer.compare(a.position, b.position));

    int fleets = 0;
    double leadTime = -1.0; // Arrival time of the current fleet leader

    // Iterate from the car closest to the target backwards
    for (int i = n - 1; i >= 0; i--) {
        double currentTime = (double)(target - cars[i].position) / cars[i].speed;
        if (currentTime > leadTime) {
            // This car is slower than the fleet in front of it,
            // so it becomes the leader of a new fleet.
            fleets++;
            leadTime = currentTime;
        }
        // Otherwise, this car will catch up and merge with the fleet ahead.
        // The number of fleets and the leadTime do not change.
    }

    return fleets;
}
```
### Algorithm
*   Create an array of `Car` objects, each storing a `position` and `speed`.
*   Sort this array of cars based on their starting `position` in ascending order.
*   Initialize a `fleets` counter to 0 and a `leadTime` variable to track the arrival time of the current leading fleet (initialized to -1.0 or 0.0).
*   Iterate through the sorted cars in reverse order, from the car closest to the target (`n-1`) to the one furthest away (`0`).
*   For each car, calculate its individual arrival time: `currentTime = (target - position) / speed`.
*   Compare `currentTime` with `leadTime`:
    *   If `currentTime > leadTime`, it means this car is slower than the fleet ahead of it and cannot catch up. It must form a new fleet. Increment `fleets` and update `leadTime` to `currentTime`, as this car is now the new bottleneck for any cars behind it.
    *   If `currentTime <= leadTime`, this car is fast enough to catch the fleet ahead. It merges into that fleet. No changes are needed for `fleets` or `leadTime`.
*   After the loop completes, return the final `fleets` count.

# Solutions
### Java

```java
class Solution { public int carFleet ( int target , int [] position , int [] speed ) { int n = position . length ; Integer [] idx = new Integer [ n ]; for ( int i = 0 ; i < n ; ++ i ) { idx [ i ] = i ; } Arrays . sort ( idx , ( i , j ) -> position [ j ] - position [ i ]); int ans = 0 ; double pre = 0 ; for ( int i : idx ) { double t = 1.0 * ( target - position [ i ]) / speed [ i ]; if ( t > pre ) { ++ ans ; pre = t ; } } return ans ; } }
```

### CPP

```cpp
class Solution { public: int carFleet ( int target , vector < int >& position , vector < int >& speed ) { int n = position . size (); vector < int > idx ( n ); iota ( idx . begin (), idx . end (), 0 ); sort ( idx . begin (), idx . end (), [ & ]( int i , int j ) { return position [ i ] > position [ j ]; }); int ans = 0 ; double pre = 0 ; for ( int i : idx ) { double t = 1.0 * ( target - position [ i ]) / speed [ i ]; if ( t > pre ) { ++ ans ; pre = t ; } } return ans ; } };
```

### Python

```python
class Solution : def carFleet ( self , target : int , position : List [ int ], speed : List [ int ]) -> int : idx = sorted ( range ( len ( position )), key = lambda i : position [ i ]) ans = pre = 0 for i in idx [:: - 1 ]: t = ( target - position [ i ]) / speed [ i ] if t > pre : ans += 1 pre = t return ans
```