Car Fleet

Problem

You are given a target position, plus arrays position and speed for a set of cars on a one-lane road.

Cars move toward the target at constant speed. A car cannot pass another car, so if it catches up, it becomes part of the same fleet. Return the number of car fleets that arrive at the target.

Intuition

The only thing that matters is the order of cars by position, from closest to the target backward.

If you look at cars in that order, each car has an arrival time t = (target - position) / speed. A car forms a new fleet only if its arrival time is greater than the fleet ahead of it. Otherwise, it catches up and merges before the target.

That means the fleet times form a monotonic structure as you scan from front to back.

Approach

impl Solution {
    pub fn car_fleet(target: i32, position: Vec<i32>, speed: Vec<i32>) -> i32 {
        let mut cars: Vec<(i32, i32)> = position.into_iter().zip(speed.into_iter()).collect();
        cars.sort_unstable_by(|a, b| b.0.cmp(&a.0));

        let mut fleets: Vec<f64> = Vec::with_capacity(cars.len());

        for (pos, spd) in cars {
            let time = (target - pos) as f64 / spd as f64;
            match fleets.last().copied() {
                None => fleets.push(time),
                Some(top) if time > top => fleets.push(time),
                _ => {}
            }
        }

        fleets.len() as i32
    }
}

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

  const fleets: number[] = [];

  for (const [pos, spd] of cars) {
    const time = (target - pos) / spd;
    if (fleets.length === 0 || time > fleets[fleets.length - 1]) {
      fleets.push(time);
    }
  }

  return fleets.length;
}

Trace

For target = 12, position = [10, 8, 5, 3, 0], speed = [2, 4, 1, 3, 1] after sorting by position descending:

The count is the number of times the arrival time strictly increases while scanning from the front.

Edge cases

• Equal arrival times — they merge into one fleet.
• Cars already sorted by position — still sort explicitly; the problem does not guarantee input order.
• One car — always one fleet.
• Fractional times — common and expected; do not round before comparing.

Takeaway

Sort by the dimension that defines interaction, then compress the rest into a monotonic stack or running frontier. Here, interaction happens only with the car or fleet directly ahead.

That is the core pattern: order first, then resolve locally.