DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Car Fleet

mediumStack and queue

Problem statement

n cars are driving on a single lane road toward the same destination, target miles away. Car i starts at position[i] miles from the start and drives at a constant speed[i] miles per hour, and no car can ever overtake the car in front of it.

If a faster car catches up to a slower one ahead of it, it has to slow down and stays right behind it for the rest of the trip — from that point on the two travel together as one fleet, moving at the slower car's speed. A fleet is any group of one or more cars travelling together like this. If a car reaches target at the exact same moment as the fleet ahead of it, it still counts as joining that fleet rather than arriving separately.

Return how many separate fleets reach target.

This is the same shape as instances rolling out one after another on a release train: a later instance can "catch up" to an earlier one that is still finishing its rollout, and once it does, the two proceed together — you want to know how many distinct rollout groups actually finish.

Examples

Example 1

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

Output: 3

Explanation: the cars at 10 and 8 meet at 12 and arrive as one fleet; the car at 0 never catches anyone, so it is its own fleet; the cars at 5 and 3 meet at 6 and travel the rest of the way together — three fleets in total.

Example 2

Input: target = 10, position = [3], speed = [3]

Output: 1

Explanation: with only one car on the road, it is automatically the only fleet.

Example 3

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

Output: 1

Explanation: the cars at 0 and 2 merge at mile 4, and that merged fleet then catches the car at 4 (which was slower) at mile 6 — all three end up in a single fleet.

Hints

Approach

Optimal: Sort + single pass

Intuition

A car can only ever merge with the fleet directly in front of it — never with one further ahead, because it isn't allowed to pass anything in between. That means if you process cars closest to target first, by the time you reach any given car you already know the true, final time of the one fleet it could possibly join. There is no need to re-check anything once it's decided, which is exactly what removes the repeated passes from the brute force.

Concretely: keep a single number, the arrival time of the fleet you most recently placed. For the next car back, compute its solo time. If that solo time is less than or equal to the time you're holding, the car catches up and joins that fleet — nothing to count, nothing to update. If it's greater, this car will still be on the road when the fleet ahead has already arrived, so it forms a brand new fleet of its own, and its time becomes the new number you compare everyone after it against.

Steps

  1. Pair each car's position with its speed, and sort the pairs by position descending — so you process the car closest to target first.
  2. Start a counter fleets = 0 and leadTime = 0.
  3. For each car, in that order, compute its solo time (target - position) / speed.
  4. If that time is strictly greater than leadTime, it starts a new fleet: increment fleets and set leadTime to this car's time.
  5. Otherwise it merges into the fleet you're already tracking — do nothing.
  6. After the loop, fleets is the answer.

Dry run

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

Sorted descending by position: (10,2), (8,4), (5,1), (3,3), (0,1).

car (position, speed) solo time compare to leadTime result
(10, 2) (12−10)/2 = 1 1 > 0 new fleet 1, leadTime = 1
(8, 4) (12−8)/4 = 1 1 > 1? no merges into fleet 1
(5, 1) (12−5)/1 = 7 7 > 1 new fleet 2, leadTime = 7
(3, 3) (12−3)/3 = 3 3 > 7? no merges into fleet 2
(0, 1) (12−0)/1 = 12 12 > 7 new fleet 3, leadTime = 12

Three cars start new fleets and two merge into the fleet directly ahead of them, giving 3 fleets in a single left-to-right pass — matching the example.

Edge cases: with zero cars the loop never runs and the answer is 0; when every car shares the same speed, no solo time is ever less than or equal to the previous leadTime (since they all fall further behind at the same rate, never catching up), so every car ends up as its own fleet.

Complexity

Time O(n log n) — Sorting the cars by position costs O(n log n) and dominates everything else; the single pass afterward that decides merges is O(n), since each car is looked at exactly once.

Space O(n) — for the sorted order and each car's computed time; O(1) extra beyond that, since only the current fleet's time needs to be remembered at any moment.

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)  # descending: closest to target first
        fleets = 0
        lead_time = 0.0
        for p, s in cars:
            time = (target - p) / s
            if time > lead_time:
                fleets += 1
                lead_time = time
        return fleets


if __name__ == "__main__":
    print(Solution().carFleet(12, [10, 8, 0, 5, 3], [2, 4, 1, 1, 3]))  # 3
    print(Solution().carFleet(10, [3], [3]))  # 1
    print(Solution().carFleet(100, [0, 2, 4], [4, 2, 1]))  # 1

Follow-up questions

No — merging never removes a car from the road, it only slows it down to match the car ahead, and the problem only counts fleets that reach target, not what happens to individual cars afterward. The algorithm doesn't need to change; a car that's merged simply never gets counted as a new fleet, and it still travels alongside its fleet the rest of the way.

If every new car starts behind every car already known (which fits a stream of cars entering behind), you can keep the algorithm running incrementally: maintain leadTime as the time of the most recently formed fleet, and each new arrival is compared only against that value, exactly as in one step of the optimal pass. You would only need to re-sort from scratch if a new car could start ahead of one already in the stream, since the "closest first" order is what the whole approach depends on.

The clean division (target - position) / speed only works because speed is constant, so the shortcut of comparing two single numbers breaks down. With variable speeds you'd need to simulate position over time directly (e.g. integrate each car's speed profile) and detect the moment, if any, that a car's position curve meets the curve of the fleet ahead of it, which is a fundamentally more expensive, numerical problem rather than a single sort-and-scan.

Frequently asked questions

The shape of the problem — a queue of things moving at different rates where a faster one can never skip past a slower one ahead, so they collapse into a single group — is the same as rollout waves catching up to each other, or requests queued behind a slow consumer that a faster one can't overtake. Interviewers use the car framing because it's easy to picture, but the pattern (a monotonic scan that merges adjacent groups) comes up anywhere ordering is preserved but rates differ.

Because a car can only merge with whatever is directly ahead of it, and "directly ahead" always means "closer to target". Processing from closest to farthest guarantees that every fleet's time is fully decided before you ever need to compare something behind it — that single guarantee is what turns the problem into one pass instead of the brute force's repeated sweeps.

You can use one (push each new fleet's time, and never need to pop, since once a fleet is set it's never revisited), but it isn't necessary — the algorithm never looks further back than the single most recent fleet, so one variable holding that fleet's time does the same job with less bookkeeping. A stack becomes useful only if a later requirement needs the whole history of fleet times, not just the most recent one.

Two cars can only be compared once their "how long until arrival" values are on the same footing, and speed differences make raw distances misleading — a car 2 miles back at speed 10 arrives before one 1 mile back at speed 1. Computing (target - position) / speed puts every car on the single scale that actually matters: time.