Leetcode - 853. Car Fleet

Medium

Dec 22, 2025

#stack

#math

853. Car Fleet

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.

You are given two integer arrays 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 single car or a group of 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.

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

Constraints:

Notes

Intuition

Cars closer to the target may slow down cars behind them. If a car behind would arrive before the car ahead, they form a fleet. Process cars from closest to farthest, tracking fleet leaders.

Implementation

Pair positions with speeds and sort by position in descending order (closest to target first). Use a stack to track arrival times of fleet leaders. For each car, calculate time to target. If this time exceeds the stack top's time, this car leads a new fleet—push its time. Otherwise, it joins an existing fleet (do nothing). The stack size is the number of fleets.

Edge-cases

Cars at the same position with different speeds still follow the same logic—the slower one determines the fleet's speed.

Time: O(n log n) — dominated by sorting
Space: O(n) — stack and sorted array

Complexity

Solution

from typing import List

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # Combine and sort by position, descending
        pos_speed = sorted([(p, s) for p, s in zip(position, speed)], key=lambda x: x[0], reverse=True)
        print(pos_speed)

        limiting_car_times = []
        for p, s in pos_speed:
            time_to_target = (target - p) / s
            if not limiting_car_times or time_to_target > limiting_car_times[-1]:
                limiting_car_times.append(time_to_target)

        return len(limiting_car_times)
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()