307. Car Fleet

Process cars from the one closest to the target backwards. A car behind joins the fleet ahead only if it would arrive no later; otherwise it starts a new fleet.

Key idea

A car cannot pass the one ahead of it. So whether two cars merge depends only on their arrival times at the target: if a car behind reaches the target at a time ≤ the car ahead, it catches up and merges; if it would arrive later, it can never catch up and forms its own fleet.

Arrival time for a car at pos with spd is (target - pos) / spd.

Walk-through

1. Pair each car as (position, speed) and sort by position descending (closest to target first).
2. Scan the sorted cars, keeping a stack of fleet-leader arrival times:
   • Compute time = (target - pos) / spd.
   • If the stack is empty or time > stack.top (the fleet ahead arrives sooner, so this car can't catch it), push time — a new fleet.
   • Otherwise time <= stack.top: this car merges into the fleet ahead (no push).
3. The number of fleets is the stack size.

Worked example

target = 12, cars sorted by position desc:

Stack size = 3 fleets.

Complexity

• Time: O(n log n) — dominated by the sort.
• Space: O(n) — the stack of arrival times.

import java.util.Arrays;

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        int[][] cars = new int[n][2];
        for (int i = 0; i < n; i++) {
            cars[i][0] = position[i];
            cars[i][1] = speed[i];
        }
        // Sort by position descending (closest to target first).
        Arrays.sort(cars, (a, b) -> b[0] - a[0]);

        int fleets = 0;
        double leadTime = 0.0;
        for (int i = 0; i < n; i++) {
            double time = (double) (target - cars[i][0]) / cars[i][1];
            if (time > leadTime) {
                fleets++;
                leadTime = time;
            }
        }
        return fleets;
    }
}