ASAPUtils
The signal
Objects move in one direction, cannot pass, and merge when a trailing object catches one ahead. Geometry becomes much simpler after transforming every car into its solo arrival time.
The key observation
For a car at position p with speed s:
arrivalTime = (target - p) / s
Process cars from closest to the target to farthest. If a trailing car’s time is less than or equal to the fleet ahead’s time, it catches that fleet. Its own time disappears. Only a strictly larger time survives as a new fleet.
int carFleet(int target, vector<int>& position, vector<int>& speed) {
vector<pair<int,int>> cars;
for (int i = 0; i < (int)position.size(); i++)
cars.push_back({position[i], speed[i]});
sort(cars.rbegin(), cars.rend());
vector<double> fleets;
for (auto [p, s] : cars) {
double time = double(target - p) / s;
if (fleets.empty() || time > fleets.back()) fleets.push_back(time);
}
return fleets.size();
}
function carFleet(target, position, speed) {
const cars = position
.map((p, i) => [p, speed[i]])
.sort((a, b) => b[0] - a[0]);
const fleets = [];
for (const [position, speed] of cars) {
const time = (target - position) / speed;
if (!fleets.length || time > fleets.at(-1)) fleets.push(time);
}
return fleets.length;
}
Walkthrough intuition
At target 12, the cars at positions 10 and 8 both have solo time 1. They meet at the target and are one fleet. The car at 5 needs 7 time units, so it cannot catch that fleet and starts another. A car behind with a smaller time catches whichever fleet is immediately ahead and adds no new stack item.
Complexity
Sorting costs O(n log n); the scan is O(n). The fleet-time stack uses O(n) space. You can reduce the
stack to one lastTime plus a counter because only the front fleet’s time is needed, but the stack
form exposes the monotonic pattern clearly.
Traps
- Sorting by speed or arrival time instead of physical position.
- Using integer division in C++; cast before dividing.
- Treating equal arrival times as separate fleets. Meeting at the target still counts as one fleet.
- Simulating movement over time. The arrival-time transformation removes time steps entirely.
Blank re-solve prompt
Count fleets by sorting once and scanning once. Explain in one sentence why a time that is no greater than the stack top disappears.