visual walkthrough
Car Fleet
MediumSort + Monotonic Stack
Sorting by position then stacking arrival times; a clever modelling problem.
The idea
Cars can't pass each other. Look at the car nearest the finish first: it sets the pace. A car behind it that would arrive sooner (or at the same time) must slow down and join its fleet; one that would arrive later stays separate.
Sorting by position and comparing arrival times against the last fleet counts the fleets in one pass.
Complexity
| approach | time | space |
|---|---|---|
| Sort + stack of fleets | O(n log n) | O(n) |