How to Explain Car Fleet in a Coding Interview (Step-by-Step)

Car Fleet is deceptively tricky — it reads like a simulation problem but solves cleanly as a monotonic stack on arrival times. The key insight isn’t about physics; it’s about recognising that a faster car behind a slower car will always be blocked, and that the stack lets you track that blocking relationship in a single pass.

In this post, you’ll learn exactly how to walk an interviewer through LeetCode 853: why you sort by position descending, how to compute arrival times, the fleet-merging logic, and every edge case worth naming.

Problem Statement

Examples

Constraints

• n == position.length == speed.length
• 1 <= n <= 105
• 0 < target <= 106
• 0 <= position[i] < target
• All positions are unique
• 0 < speed[i] <= 106

What Is the Problem?

“Cars travel on a single lane toward a target — no passing allowed. A faster car behind a slower one will catch up and then travel at the slower speed as one fleet. I need to count how many distinct fleets arrive at the target. The key observation is that a car can only be blocked by a car that is ahead of it — so I should process cars from closest to the target first.”

Stating the no-passing rule and the direction of blocking upfront shows the interviewer you’ve identified the physical constraint that drives the entire solution.

Step 1: Compare Approaches Before Jumping to Code

“There is no need to simulate. The question of how many fleets arrive is entirely determined by arrival times. If a car behind arrives at the target no later than the car ahead, it will have caught up — they form one fleet. Sorting by position descending lets me process cars from front to back and compare each car to the fleet immediately ahead of it.”

The Key Insight — Arrival Times Determine Fleets

“The word ‘unobstructed’ is critical — I compute arrival time assuming no car is in the way. If this theoretical time is still slower than the car ahead, it will never catch up even with free road. If it’s faster or equal, it catches up exactly at or before the target and joins the fleet. Fleets travel together, so only the slowest (first-pushed) time per fleet is what future cars compare against.”

Step 2: Explain the Algorithm in Plain English

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

First, compute each car’s arrival time and sort by position descending:

Stack at the end: [1.0, 7.0, 12.0] → 3 fleets ✓

“Car at position 8 has arrival time 1.0 — same as car at position 10. Even though car 8 is faster, it can’t pass car 10. It catches up exactly at the target and merges. Car at position 3 has arrival time 3.0 which is less than 7.0 (the fleet at position 5), so it catches that fleet before the target and merges.”

Stack Trace Step by Step

Step 3: Talk Through the Code

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # Pair cars and sort by position descending (closest to target first)
        cars  = sorted(zip(position, speed), key=lambda x: -x[0])
        stack = []   # Stores arrival times of distinct fleets

        for pos, spd in cars:
            time = (target - pos) / spd   # Unobstructed arrival time

            # A new fleet forms only if this car arrives AFTER the fleet ahead
            # (i.e. it can never catch up, even on an open road)
            if not stack or time > stack[-1]:
                stack.append(time)
            # else: time <= stack[-1] → car catches up → merges, do nothing

        return len(stack)

Draw attention to the condition time > stack[-1] — strictly greater than. Equal arrival time means the car catches up exactly at the target and still merges. Using >= here would over-count fleets. This is the most common off-by-one mistake on this problem.

Step 4: Highlight Edge Cases

Step 5: State Time and Space Complexity

"Sorting is O(n log n). The single pass over the sorted array is O(n) — each car is processed once, with one O(1) push or skip. Space is O(n) for the sorted pairs and the stack. There is no way to go below O(n log n) time here unless the positions were already sorted, in which case the pass alone would be O(n)."

Interview Checklist for Car Fleet

• Restate — "count fleets arriving at target; a car that catches the one ahead merges into it"
• State the no-passing rule and explain that blocking only comes from cars ahead
• Explain why simulation is overkill — arrival times are sufficient
• State the arrival time formula: (target − position) / speed
• Explain why you sort by position descending — process closest to target first
• Describe the stack logic: push only if arrival time is strictly greater than the top
• Emphasise strictly greater-than — equal arrival time = merge, not a new fleet
• Return stack length — each element represents one fleet
• Call out: single car, all-same-speed, all-merge, equal arrival times
• State O(n log n) time and O(n) space

Related Problems to Practice

If you can solve Car Fleet cleanly, try these next: