Car Fleet

Examples

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

The car at 10 reaches the destination on its own. The car at 8 is fast enough to catch up to it first, and they arrive together as one fleet. The car at 5 travels alone at first, but the car at 3 (which is faster) catches up to it, forming a second fleet. The car at 0 never catches anyone, forming a third fleet by itself. That's 3 fleets in total.

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

With only one car on the road, it's automatically its own fleet.

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

The car at 0 is the fastest and catches up to the car at 2, and that combined group in turn catches up to the slowest car, at 4. Everyone ends up traveling together as a single fleet.

Constraints

• n == position.length == speed.length

• 1 <= n <= 10^5

• 0 < target <= 10^6

• 0 <= position[i] < target

• Every value in position is unique.

• 0 < speed[i] <= 10^6

Approach

Since cars can never pass each other, a car either reaches the destination entirely on its own, or it catches up to the car (or group of cars) ahead of it and permanently joins that fleet, slowing to match its pace. The key insight is that this only ever depends on the car directly ahead by position — if a car doesn't catch that one, it can't possibly catch anything further ahead either, since the car in front of it is equally blocked.

So: compute, for every car, how long it would take to reach the destination if it were driving completely alone. Then process the cars in order from closest to the destination to farthest. Keep track of the arrival time of the fleet formed most recently. If the next car (further back) would arrive at or before that time on its own, it's guaranteed to catch up and merge into that fleet — it doesn't start a new one. If it would arrive later, it can never catch up, so it becomes the leader of a brand new fleet. The final count of fleets formed this way is the answer.

Solutions

Brute Force — Repeatedly Merge Adjacent Cars

Sort cars by position. Repeatedly scan through them and merge any adjacent pair where the car behind would arrive at or before the car ahead of it (meaning it's caught up), replacing the pair with a single merged group that behaves like the front car from then on. Keep re-scanning until a full pass produces no more merges.

function carFleet(target, position, speed) {
  let groups = position.map((p, i) => ({ pos: p, time: (target - p) / speed[i] }));
  groups.sort((a, b) => a.pos - b.pos); // farthest from target (rear-most) first

  let merged = true;
  while (merged) {
    merged = false;
    const next = [];
    let i = 0;
    while (i < groups.length) {
      if (i + 1 < groups.length && groups[i].time <= groups[i + 1].time) {
        // the rear group catches the group ahead of it; they become one fleet
        next.push({ pos: groups[i + 1].pos, time: groups[i + 1].time });
        i += 2;
        merged = true;
      } else {
        next.push(groups[i]);
        i += 1;
      }
    }
    groups = next;
  }

  return groups.length;
}

Time: O(n²) in the worst case, on top of the initial O(n log n) sort · Space: O(n)

Optimal — Sort + Monotonic Stack

Compute each car's solo arrival time, then process cars from closest to the destination to farthest, keeping a stack of fleet arrival times. A car merges into the fleet ahead if its own time is less than or equal to the time on top of the stack; otherwise it leads a brand new fleet.

function carFleet(target, position, speed) {
  const cars = position
    .map((p, i) => [p, speed[i]])
    .sort((a, b) => b[0] - a[0]); // closest to target first

  const stack = [];
  for (const [pos, spd] of cars) {
    const time = (target - pos) / spd;
    if (stack.length === 0 || time > stack[stack.length - 1]) {
      stack.push(time);
    }
    // otherwise this car catches up to the fleet ahead before the target,
    // so it merges instead of forming a new fleet
  }

  return stack.length;
}

Time: O(n log n), dominated by the sort · Space: O(n)