LeetCode 853: Car Fleet

Problem Restatement

There are n cars driving toward the same destination.

The destination is at position target.

For each car:

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

Function shape:

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

Examples

Example 1:

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

Compute how long each car needs to reach the target:

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

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:

3

Example 2:

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

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

1

Example 3:

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

Times to target:

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

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:

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.

cars = list(zip(position, speed))

Sort cars by position in descending order.

cars.sort(reverse=True)

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

Maintain:

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

The scan after sorting takes O(n) time.

Implementation

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:

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

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

For example:

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

becomes:

[10, 8, 5, 3, 0]

Then we keep two values:

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:

time = (target - pos) / spd

If this car needs more time than the fleet ahead:

if time > slowest_time_ahead:

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

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

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: