Stack · LC #853
Car Fleet
Determine how many car fleets arrive at a destination by sorting cars by position and using a stack to detect when a trailing car catches up to the one ahead.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
There are `n` cars at different positions on a one-lane road heading to the same `target`. You are given two integer arrays `position` and `speed`. A car can never pass another car ahead of it, but it may catch up and form a fleet traveling at the slower car's speed. Return the number of car fleets that will arrive at the target.
Sample I/O
Input: target=12, position=[10,8,0,5,3], speed=[2,4,1,1,3] Output: 3 Input: target=10, position=[3], speed=[3] Output: 1 Input: target=100, position=[0,2,4], speed=[4,2,1] Output: 1
Time: O(n log n) · Space: O(n)
Intuition
How to Think About It
Intuition
Process cars from closest to the target to farthest. A car behind can only catch up to the car immediately ahead of it - if the trailing car arrives at the target earlier than (or equal to) the leading car, it joins the fleet and takes the leading car's slower arrival time. The stack maintains the fleet leaders' arrival times in a monotonically increasing order.
Core Concept
Compute each car's time to reach the target: `(target - position) / speed`. Sort cars by position in descending order (closest-first). Iterate and push each car's time onto a stack only if it is strictly greater than the current top - meaning it forms a new fleet. If its time is ≤ the top, it would catch up to the car ahead before target and merges into that fleet. Stack size = fleet count.
When to use
Problems where sorted order reveals a natural "catches up" or "merges" relationship between adjacent elements. Monotonic stack applied after sorting.
When NOT to use
Multiple lanes (passing is allowed). When fleet membership changes at intermediate checkpoints rather than only at the destination.
Key Insights
What to Know Cold
- Sort descending by position so adjacent cars in the sorted array are actually adjacent on the road.
- A car with a lower arrival time than the car ahead will catch up and join its fleet - do NOT push it.
- Equal arrival times also form a fleet (the trailing car arrives exactly at the target simultaneously).
- The stack is monotonically increasing in arrival time (from bottom to top) - any car with smaller time merges into the top fleet.
- The actual stack contents are arrival times, not positions or car indices.
1 example
Worked Examples
Fleet detection trace on target=12, position=[10,8,0,5,3], speed=[2,4,1,1,3]
Five cars; expected 3 fleets.
Times: car@10→1.0, car@8→1.0, car@5→7.0, car@3→3.0, car@0→12.0. Sorted desc by pos: (10,1.0),(8,1.0),(5,7.0),(3,3.0),(0,12.0). Stack: push 1.0; 1.0 ≤ 1.0 → skip (merges); push 7.0; 3.0 ≤ 7.0 → skip; push 12.0. Stack=[1.0,7.0,12.0] → 3 fleets.
carFleet(12, [10,8,0,5,3], [2,4,1,1,3]); // 3 carFleet(10, [3], [3]); // 1
Output: 3
Shows the equal-time merge (car@8 joins car@10 fleet) and the slow-car blocking (car@3 is absorbed by car@5 fleet despite being faster because car@5 is ahead and slower).