Car Fleet

MediumStackArrayStackSorting

Problem

A group of cars travels along a single lane toward the same destination, each starting at its own position with its own constant speed. A faster car that catches a slower one ahead cannot pass it: it must slow to the slower car's speed, and the two count as one fleet for the rest of the trip. Given each car's starting position and speed, determine how many distinct fleets ultimately reach the destination.

Example. With a target of 12 and cars at positions [10, 8, 0, 5, 3] moving at speeds [2, 4, 1, 1, 3], three fleets arrive.

Key idea

Simulating the positions of every car over time is fiddly and imprecise. A cleaner approach ignores position over time and instead asks how long each car would take to reach the destination if nothing blocked it: that time is simply the remaining distance divided by its speed.

Process the cars from the one closest to the destination back to the one farthest away, since a car can only be slowed by a car ahead of it, never behind. Track the arrival time of the fleet currently leading the pack. A car forms a brand-new fleet if its own unobstructed arrival time is strictly greater than the leading time, meaning it never actually catches up. Otherwise it catches the car ahead before the destination and merges into that fleet, adopting the leader's slower arrival time as the new threshold for the next car.

Solution

function carFleet(target: number, position: number[], speed: number[]): number {
  // Process cars from closest to the target to farthest, since only a car ahead can slow one behind.
  const cars = position
    .map((pos, i) => ({ pos, speed: speed[i] }))
    .sort((a, b) => b.pos - a.pos);

  let fleets = 0;
  let leadingArrival = -Infinity;

  for (const car of cars) {
    const arrival = (target - car.pos) / car.speed; // Time to reach target if unobstructed.
    // Strictly later than the current leader means this car never catches up: a new fleet.
    if (arrival > leadingArrival) {
      fleets++;
      leadingArrival = arrival;
    }
  }

  return fleets;
}

Complexity

  • Time: O(n log n). Dominated by sorting the cars by starting position.
  • Space: O(n). For storing arrival times alongside the sorted positions.

Watch out for

  • Sort by starting position before sweeping; process order matters, not input order.
  • Compare each car only against the current leading arrival time, not against every car behind it.
  • A tie in arrival times still counts as merging into one fleet, not two separate fleets.

Pattern

This reduces a physical catch-up simulation to sweeping through precomputed values while tracking one running threshold, the same instinct behind monotonic stack problems like daily temperatures.

Related questions