Car Fleet

The problem

target miles down a single-lane road. Car i starts at position[i] with speed speed[i]. A faster car cannot pass a slower car ahead — it catches up and forms a fleet traveling at the slower speed. Fleets never pass each other. How many fleets arrive at the target?

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

Brute force

Simulate second-by-second. Messy with floats and “catch-up” events. O(target × n) worst and ugly. Don’t code it.

Key idea: time to target

For each car: time = (target - position) / speed.

Process cars from closest to target → farthest (sort position descending):

• The lead car always forms a fleet (nothing ahead).
• A car behind joins the fleet ahead if its time ≤ the fleet’s arrival time (it catches up before or at target).
• Otherwise it becomes a new slower fleet.

Monotonic stack of fleet arrival times (increasing as we go backward).

function carFleet(
  target: number,
  position: number[],
  speed: number[]
): number {
  const n = position.length;
  const cars = position
    .map((p, i) => ({ p, t: (target - p) / speed[i] }))
    .sort((a, b) => b.p - a.p); // near target first

  let fleets = 0;
  let slowest = 0; // max time among fleets already formed (looking from front)

  for (const { t } of cars) {
    // strictly slower to arrive → cannot catch fleet ahead → new fleet
    if (t > slowest) {
      fleets++;
      slowest = t;
    }
    // else catches up / merges; no new fleet
  }

  return fleets;
}

Stack form (same idea):

function carFleetStack(
  target: number,
  position: number[],
  speed: number[]
): number {
  const cars = position
    .map((p, i) => [p, (target - p) / speed[i]] as const)
    .sort((a, b) => b[0] - a[0]);

  const stack: number[] = []; // times of fleets from front

  for (const [, t] of cars) {
    if (stack.length === 0 || t > stack[stack.length - 1]) {
      stack.push(t);
    }
  }
  return stack.length;
}

Time	O(n log n) sort
Space	O(n)

Walk sample

Positions near→far: 10 (t=1), 8 (t=1), 5 (t=7), 3 (t=3), 0 (t=12)

• t=1 → fleet, slowest=1
• t=1 → merges
• t=7 → new fleet, slowest=7
• t=3 → merges into 7 (arrives earlier, blocked)
• t=12 → new fleet

Fleets = 3.

Edge cases

• One car → 1
• Same position — usually unique positions in constraints
• Car already at target — time 0
• Floating compare: use > carefully; equal times merge

Common mistakes

• Sorting by speed not position
• Processing from back of the road (farthest first) without flipping the merge logic
• Integer division truncating times

Interview delivery

1. Single lane, no pass → catch-up fleets.
2. Time-to-target metric.
3. Sort by position descending; count new slower fleets.
4. O(n log n).

Related

• Daily Temperatures — monotonic stack
• Valid Parentheses
• Jump Game — forward reach greedy
• JavaScript Interview Guide

Further reading

• LeetCode 853 — Car Fleet
• MDN: Array.sort