Problem Overview

We are given n cars traveling toward the same destination on a one-lane highway.

Each car has:

• a starting position
• a speed
• the same destination at target

A key rule is that cars cannot pass each other. If a faster car catches up to a slower car ahead of it, it becomes part of the same fleet and continues at the slower car’s speed.

We need to return the number of car fleets that eventually reach the destination.

Key Idea

Instead of simulating the movement of every car, we calculate how long each car would take to reach the destination.

For a car at position p with speed s:

time = (target - p) / s

Now, the important part is the order.

We sort cars by position in descending order, meaning we process the cars closest to the destination first.

Why?

Because a car behind can only catch up to cars ahead of it. So we compare each car’s arrival time with the fleet ahead.

Stack-Based Solution

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)

        stack = []

        for p, s in pair:
            stack.append((target - p) / s)

            if len(stack) >= 2 and stack[-1] <= stack[-2]:
                stack.pop()

        return len(stack)

Explanation

First, we combine each car’s position and speed into a pair:

pair = [(p, s) for p, s in zip(position, speed)]

Then we sort the cars from closest to the destination to farthest:

pair.sort(reverse=True)

For each car, we calculate its time to reach the destination and push it onto the stack.

If the current car takes less time than or equal to the fleet ahead, that means it will catch up before or exactly at the destination.

So it becomes part of the fleet ahead, and we remove it from the stack:

if len(stack) >= 2 and stack[-1] <= stack[-2]:
    stack.pop()

At the end, the number of items left in the stack is the number of fleets.

Optimized Variable-Based Solution

We can solve the same problem without using a stack.

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)):
            currTime = (target - pair[i][0]) / pair[i][1]

            if currTime > prevTime:
                fleets += 1
                prevTime = currTime

        return fleets

Explanation

The first car closest to the destination always forms at least one fleet.

So we start with:

fleets = 1

We store its arrival time as prevTime.

Then, for every car behind it, we calculate currTime.

If:

currTime <= prevTime

then the current car catches up to the fleet ahead, so it does not create a new fleet.

But if:

currTime > prevTime

then the current car is too slow to catch up, so it forms a new fleet.

In that case, we increase the fleet count and update prevTime.

Why Sorting Matters

Sorting by position in descending order lets us process cars from front to back.

This is important because only cars behind can merge into cars ahead. A car in front never needs to care about a car behind unless that car catches up.

By moving from closest to farthest, we only need to track the slowest reachable fleet time ahead.

Complexity Analysis

Let n be the number of cars.

Sorting takes:

O(n log n)

Looping through the cars takes:

O(n)

So the total time complexity is:

O(n log n)

The stack solution uses:

O(n)

extra space.

The variable-based solution uses:

O(1)

extra space, not counting the sorted pair list.

Final Thoughts

The main trick in this problem is realizing that we do not need to simulate the cars moving.

We only need to calculate each car’s arrival time and process the cars from closest to farthest from the destination.

If a car behind arrives sooner than or at the same time as the fleet ahead, it merges into that fleet. Otherwise, it becomes a new fleet.

This makes the problem much simpler and gives us an efficient solution.