Car Fleet Problem — Stack-Based Arrival Time Solution

Cars drive toward a target on a single-lane road. A faster car behind a slower car will catch up and form a fleet — they travel together at the slower car’s speed. How many fleets arrive at the target?

This is LeetCode 853.

Understanding the Problem

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

Car at pos 10, speed 2: arrives at (12-10)/2 = 1.0
Car at pos  8, speed 4: arrives at (12-8)/4  = 1.0
Car at pos  5, speed 1: arrives at (12-5)/1  = 7.0
Car at pos  3, speed 3: arrives at (12-3)/3  = 3.0
Car at pos  0, speed 1: arrives at (12-0)/1  = 12.0

Answer: 3 fleets

Key Insight

Sort cars by position (closest to target first). Then process from closest to farthest:

• If a car behind would arrive before or at the same time as the car ahead, it joins that fleet (it catches up)
• If a car behind would arrive later, it forms a new fleet (it is slower and never catches up)

A car can never pass the car directly ahead. So we only compare adjacent cars.

Solution

def car_fleet(target: int, position: list[int], speed: list[int]) -> int:
    """
    Count number of car fleets.
    LeetCode 853.
    Time: O(n log n), Space: O(n)
    """
    # Pair position with arrival time, sort by position descending
    cars = sorted(zip(position, speed), reverse=True)

    stack = []  # stores arrival times of fleet leaders

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

        if not stack or arrival > stack[-1]:
            # This car is slower — forms new fleet
            stack.append(arrival)
        # else: this car catches up to the fleet ahead — joins it

    return len(stack)

Step-by-Step Trace

target = 12
Cars sorted by position (descending):
  pos=10, spd=2 → arrival = (12-10)/2 = 1.0
  pos=8,  spd=4 → arrival = (12-8)/4  = 1.0
  pos=5,  spd=1 → arrival = (12-5)/1  = 7.0
  pos=3,  spd=3 → arrival = (12-3)/3  = 3.0
  pos=0,  spd=1 → arrival = (12-0)/1  = 12.0

Processing:
Car(10,2) arrival=1.0  stack empty → new fleet    stack=[1.0]
Car(8,4)  arrival=1.0  1.0 <= 1.0 → joins fleet   stack=[1.0]
Car(5,1)  arrival=7.0  7.0 > 1.0 → new fleet     stack=[1.0, 7.0]
Car(3,3)  arrival=3.0  3.0 <= 7.0 → joins fleet   stack=[1.0, 7.0]
Car(0,1)  arrival=12.0 12.0 > 7.0 → new fleet    stack=[1.0, 7.0, 12.0]

Answer: 3 fleets ✓

Visual: Fleet Formation on the Road

Target = 12
─────────────────────────────────────── target
Position:  0    3    5         8  10   12

Car 0: pos=0, speed=1    ───→           arrives at t=12
Car 3: pos=3, speed=3    ──────→        arrives at t=3 (catches car 5)
Car 5: pos=5, speed=1    ───→           arrives at t=7
Car 8: pos=8, speed=4    ────────→      arrives at t=1 (catches car 10)
Car10: pos=10, speed=2   ────→          arrives at t=1

Fleet 1: {Car10, Car8}  → arrive at t=1.0
Fleet 2: {Car5, Car3}   → arrive at t=7.0 (Car3 slows down)
Fleet 3: {Car0}          → arrive at t=12.0

Why Sort by Position Descending?

We process from closest to target first because:

1. The car closest to target cannot be blocked by anyone
2. Each subsequent car can only be blocked by the car directly ahead
3. If a car arrives later than the fleet ahead, it can never catch up — new fleet

Sorting ascending and traversing in reverse works too:

def car_fleet_alt(target, position, speed):
    cars = sorted(zip(position, speed))
    stack = []

    for pos, spd in reversed(cars):
        arrival = (target - pos) / spd
        if not stack or arrival > stack[-1]:
            stack.append(arrival)

    return len(stack)

Without Stack (Simpler)

Since we only compare with the last fleet leader, a simple counter works:

def car_fleet_simple(target, position, speed):
    """
    No explicit stack needed — just track last arrival time.
    """
    cars = sorted(zip(position, speed), reverse=True)
    fleets = 0
    last_arrival = 0

    for pos, spd in cars:
        arrival = (target - pos) / spd
        if arrival > last_arrival:
            fleets += 1
            last_arrival = arrival

    return fleets

This is equivalent to the stack approach but uses O(1) space.

Edge Cases

# Single car → always 1 fleet
assert car_fleet(10, [5], [1]) == 1

# All same speed → depends on spacing
# If all arrive at different times → n fleets
assert car_fleet(10, [0, 2, 4], [2, 2, 2]) == 3

# All arrive at same time → 1 fleet
assert car_fleet(12, [4, 0, 2], [3, 6, 4]) == 1  # all arrive at t=2.67

# Empty
assert car_fleet(10, [], []) == 0

# Two cars, faster behind → 1 fleet
assert car_fleet(10, [0, 5], [10, 1]) == 1

# Two cars, slower behind → 2 fleets
assert car_fleet(10, [0, 5], [1, 2]) == 2

Complexity

When to Use This Pattern

• Collision/merge problems: When entities moving at different speeds merge
• Monotonic stack on sorted data: Sort first, then stack comparison
• Simulation simplification: Instead of simulating movement, compute arrival times
• Interval-like reasoning: Fleet formation is really about comparing intervals of arrival

Follow-up: Car Fleet II (LeetCode 1776)

The harder version asks: for each car, when does it collide with the car ahead? This requires processing from right to left with a stack tracking the remaining cars and their collision times.

Related Problems

• Asteroid Collision — similar collision simulation
• Daily Temperatures — monotonic stack pattern
• Online Stock Span — stack comparison from one direction