Car Fleet

How it works

After sorting cars from closest to the target to farthest, we calculate how long each one needs to reach the target.
A car forms a new fleet only if it takes longer than the fleet in front of it.
If it takes the same time or less, it will eventually catch up and merge into that fleet.
So instead of using a stack, we just keep track of the most recent fleet time.

Steps

1. Pair each car’s position with its speed and sort descending by position.
2. Start with the first car forming the first fleet.
3. Keep track of the fleet's time (prevTime) - the time of the car closest to the target.
4. For each remaining car:
   • Compute its time to reach the target.
   • If this time is greater than prevTime, it cannot catch up and forms a new fleet.
     • Increase fleet count.
     • Update prevTime to this new time.
   • Otherwise, it merges with the existing fleet and do nothing.
5. Return the number of fleets.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(n)

Things to watch for

Sorting in the Wrong Order

Sorting cars by position in ascending order (farthest from target first) instead of descending order causes incorrect fleet merging. Cars must be processed from closest to the target first, since a car behind can only merge with the fleet ahead of it.

Using Strict Less Than for Fleet Merging

Using < instead of <= when comparing arrival times misses the case where two cars arrive at exactly the same time. If a car behind arrives at the same time or earlier than the car ahead, it joins that fleet.

Integer Division Instead of Float Division

In languages like Java or C++, dividing two integers results in integer division, which truncates the decimal part. Since arrival times are often fractional, this leads to incorrect comparisons and wrong fleet counts.

from typing import List

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        pair = [(p, s) for p, s in zip(position, speed)]
        pair.sort(reverse=True)

        fleets = 1
        prevTime = (target - pair[0][0]) / pair[0][1]
        for i in range(1, len(pair)):
            currCar = pair[i]
            currTime = (target - currCar[0]) / currCar[1]
            if currTime > prevTime:
                fleets += 1
                prevTime = currTime
        return fleets

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        int n = position.size();
        vector<pair<int, int>> pair;
        for (int i = 0; i < n; i++) {
            pair.push_back({position[i], speed[i]});
        }
        sort(pair.rbegin(), pair.rend());

        int fleets = 1;
        double prevTime = (double)(target - pair[0].first) / pair[0].second;
        for (int i = 1; i < n; i++) {
            double currTime = (double)(target - pair[i].first) / pair[i].second;
            if (currTime > prevTime) {
                fleets++;
                prevTime = currTime;
            }
        }
        return fleets;
    }
};