Car Fleet

MediumStackNeetCode 150MidOpen on LeetCodeUpdated Nov 11, 2026

Cars drive toward a destination at mile target along a one-lane road. Car i starts at mile position[i] and drives at speed[i] miles per hour, and every starting position is different. A car can't pass the one ahead; when it catches up, it slows down and the two travel together as a fleet at the slower speed. Cars that meet exactly at the destination also count as one fleet. Return how many fleets arrive at the destination.

Examples

target = 20, position = [0,4,10,15], speed = [4,1,2,5] returns 3

Alone, the cars would arrive after 5, 16, 5, and 1 hours. The car at 15 arrives first by itself, the car at 10 arrives alone after 5 hours, and the car at 0 catches the slow car at 4, so those two arrive together after 16 hours.

target = 10, position = [0,4], speed = [2,1] returns 1

The car at 4 needs 6 hours. The car at 0 would need only 5, so it catches up before the destination and they finish as one fleet.

target = 10, position = [3], speed = [2] returns 1

A single car is a fleet of one.

Constraints

n == position.length == speed.length
1 <= n <= 10^5
0 < target <= 10^6
0 <= position[i] < target, and all positions are distinct.
0 < speed[i] <= 10^6

Hints

Hint 1

A car can only be held up by cars in front of it. Which order should you look at the cars in?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Compute each car's arrival time if it drove alone, (target - position) / speed, and process the cars from the one closest to the destination backward. A car joins the fleet ahead of it when its own time is no greater than that fleet's time, since it would catch up by the finish. Otherwise it is slower than everything ahead and starts a new fleet, whose time becomes the new bar to beat. This is a monotonic stack of fleet times, and only its top matters, so a single variable is enough. Sorting dominates: O(n log n) time, O(n) space.

Time

O(n log n)

Space

O(n)

Pitfall

Comparing speeds or positions instead of arrival times. A fast car far behind may never catch up, and a slow car just behind may still be caught. Only the time to the destination settles it.

Solutions

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> position[b] - position[a]);
        int fleets = 0;
        double slowest = 0;
        for (int i : order) {
            double time = (double) (target - position[i]) / speed[i];
            if (time > slowest) {
                fleets++;
                slowest = time;
            }
        }
        return fleets;
    }
}

class Solution:
    def carFleet(self, target: int, position, speed) -> int:
        cars = sorted(zip(position, speed), reverse=True)
        fleets = 0
        slowest = 0.0
        for pos, spd in cars:
            time = (target - pos) / spd
            if time > slowest:
                fleets += 1
                slowest = time
        return fleets