Car Fleet
Medium · Arrays & Hashing · Array · Stack · Sorting · Monotonic Stack
Problem
n cars drive along a one-lane road toward a destination at mile target. Car i starts at mile position[i] and drives at speed[i] miles per hour. All starting positions are different.
A car can never pass another. When it catches up with a slower car ahead, it slows down and the two drive on together at the slower speed: they form a fleet. A car on its own is a fleet too. A car that catches a fleet exactly at target counts as part of that fleet.
Return the number of fleets that arrive at the destination.
Examples
Input: target = 15, position = [12,9,1,6,4], speed = [3,6,2,1,5] Output: 2
The cars at 12 and 9 both need 1 hour and arrive together. The car at 6 needs 9 hours, and the cars at 4 (2.2 hours) and 1 (7 hours) are held up behind it.
Input: target = 10, position = [6,2,0], speed = [1,2,5] Output: 1
The front car needs 4 hours, and the cars behind would be faster, so everyone ends up behind it.
Input: target = 20, position = [0,10], speed = [1,5] Output: 2
The front car arrives after 2 hours and the back car after 20, so they never meet.
Constraints
- n == len(position) == len(speed)
- 1 <= n <= 10^5
- 0 < target <= 10^6
- 0 <= position[i] < target, all different
- 0 < speed[i] <= 10^6
Approaches
- Check every car ahead — time O(n²), space O(1)
Follow-up
The arrival times of the fleet leaders, read from the front car backward, strictly increase: they form a monotonic stack, and the answer is its height. If the destination moves or cars enter the road over time, the same rule still applies to whatever cars are behind a given point: only the slowest arrival time ahead matters.
Related problems
Start free on Cariara · Coding problems · System design studio
