853. Car Fleet — DSA Atlas

853

MediumMonotonic Stack and Monotonic QueueSorting plus a monotonic stack of arrival timesArrival-time monotonic stack

Car Fleet

Cars drive toward a destination at position target on a one-lane road. Car i starts at position[i] moving at speed[i]; a faster car that catches a slower one ahead cannot pass and joins it, forming a fleet that then moves at the slower car's speed. Cars arriving at the destination together count as one fleet. Return how many distinct fleets reach the target.

Open official problem prompt ↗

In plain English

Count how many groups of cars ultimately reach the destination as distinct clusters, given that faster cars stack up behind slower ones.

Picture it like this

Traffic on a single-lane road with no passing: a speeding car eventually tailgates a slowpoke ahead and is forced to crawl behind it. From the finish line you only count the distinct bumper-to-bumper clusters that cross.

Example

Input: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
Output: 3
Why: Cars at 10 and 8 both reach the target at time 1 and form one fleet; the cars at 5 and 3 merge into a second fleet; the car at 0 arrives last as a third fleet.

Constraints

n == position.length == speed.length1 <= n <= 10^50 < target <= 10^60 <= position[i] < target0 < speed[i] <= 10^6All position values are unique

Pattern lesson

See the pattern, then code

Arrival-time monotonic stack

↗

Monotonic Stack and Monotonic Queue

Next greater or smaller value, nearest boundary, histogram, or window extremum.. Sort cars from closest-to-target to farthest. A car behind forms a new fleet only if its time-to-reach exceeds the current fleet leader's time; otherwise it catches up and merges. The running 'lead time' behaves like a monotonic stack top.

New words, made simpleKnow these before the algorithm

Fleet: A group of cars traveling bumper-to-bumper because faster cars caught the slower one ahead.
Time to target: (target - position) / speed — how long a car alone would take to arrive.
Lead time: The arrival time of the current front-most fleet; a car merges if it would arrive no later.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Simulate positions over time

Depends on a time granularity and is both slow and imprecise.

Advance every car step by step, merging speeds when one catches another.

Time O(n * T)Space O(n)

Best choiceSort by position, compare arrival times

Sorting dominates; a single linear pass then counts fleets exactly.

Process cars nearest-to-target first; a car starts a new fleet only if its solo arrival time exceeds the fleet ahead of it.

Time O(n log n)Space O(n)

The rule we keep true

Invariant

Processing cars from closest to farthest, 'cur' holds the arrival time of the frontmost fleet seen so far; any later car with time <= cur is absorbed into it.

Why this is correct

Reasoning

A car closer to the target defines a fleet lead. A car behind it (larger distance) that would arrive at the same time or sooner must have caught up and cannot pass, so it merges and inherits the slower lead time. Only a car whose solo time strictly exceeds the current lead escapes merging and becomes a new, later-arriving fleet. Scanning in decreasing position order guarantees each car is compared against the correct fleet ahead of it.

The algorithm in three movesSay these aloud before coding

1Pair each position with its speed and sort by position descending

sorted pos desc: 10,8,5,3,0

2Compute time = (target - position) / speed for each car in that order

times: 1.0, 1.0, 7.0, 3.0, 12.0

3Track the current fleet's arrival time; if a car's time is strictly greater, it is a new fleet

fleets counted at times 1.0, 7.0, 12.0 -> 3

4Count each new fleet and update the lead time to it

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

100

1 · Readpositions with speeds

2 · AskWhat order to process?

3 · Update state(10,2),(8,4),(5,1),(3,3),(0,1)

4 · ResultDescending by position

Key takeaway

Cars sorted by position from nearest the target (left) to farthest; a new fleet forms whenever arrival time jumps above the current lead.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Pair and sort descending
zip couples each position to its speed; reverse sort puts the car nearest the target first.
2
Lines 4-5Fleet counter and lead time
fleets counts clusters; cur remembers the frontmost fleet's arrival time.
3
Lines 6-10Merge-or-new decision
A strictly greater time means the car cannot catch the fleet ahead, so it starts a new fleet and becomes the new lead.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A single car is always exactly one fleet
Two cars arriving at the identical time count as one fleet
A slow car ahead of many fast cars absorbs them all into one fleet
A car already faster but starting behind still merges if arrival times coincide

Common beginner mistakes

Sorting ascending by position instead of descending compares cars against the wrong neighbor
Using >= instead of > would wrongly split cars that arrive simultaneously
Integer division loses the fractional arrival time and misclassifies merges — use float division
Comparing positions at a fixed time instead of arrival times misses cars that merge exactly at the target

Check your understanding

Why is comparing arrival times sufficient instead of tracking where cars actually meet?

Car Fleet

Car Fleet

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Monotonic Stack and Monotonic Queue