524. Car Fleet
n cars share a single lane heading to a destination at mile target. Car i starts at mile position[i] (all starting miles are distinct) and cruises at speed[i] miles per hour.
No car can pass the car ahead of it. When a faster car catches up, it slows to match and the two travel on together as one fleet; a fleet moves at the speed of its slowest, frontmost car. A car that catches another one exactly at the destination still merges into that fleet.
Given the integer target and the arrays position and speed, return the number of distinct fleets that arrive at the destination.
Example 1:
Input: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
Output: 3
Explanation: The car at mile 10 (speed 2) and the car at mile 8 (speed 4) both need 1 hour, so the second one catches the first exactly at mile 12 — one fleet. The car at mile 3 (speed 3) overtakes-in-spirit the slow car at mile 5 well before the target and they finish together — a second fleet. The car at mile 0 (speed 1) never catches anyone — a third fleet.
Example 2:
Input: target = 100, position = [0, 2, 4], speed = [4, 2, 1]
Output: 1
Explanation: The rearmost car is the fastest: it catches the middle car, the pair catches the front car, and everyone rolls in as a single fleet.
Example 3:
Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation: A single car is its own fleet.
Constraints:
- 1 ≤ n ≤ 10⁵
- position.length == speed.length == n
- 0 ≤ position[i] < target ≤ 10⁶
- All position[i] values are distinct.
- 1 ≤ speed[i] ≤ 10⁶
Hints:
Blocking aside, each car is fully described by one number: its unhindered arrival time (target - position[i]) / speed[i]. A car can only ever be delayed by cars that start ahead of it.
Sort the cars by starting position, closest to the target first, and walk that order. The car you are looking at merges into the fleet directly ahead exactly when its own arrival time is less than or equal to that fleet's arrival time.
Keep a stack of fleet-leader times. For each car's time t: if t <= the time on top of the stack, the car joins that fleet (push nothing); otherwise t starts a new fleet (push it). The answer is the final stack size — and since the kept times only ever increase, a single running maximum works too.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
Expected output: 3