Car Fleet

The key idea

Sort cars by starting position from closest-to-target to farthest. Walk from the front car backward: a car behind joins the fleet ahead only if its time-to-target is less than or equal to the fleet's time. A car that takes strictly longer can never catch up, so it starts a new fleet. The number of new fleets started is the answer.

Problem

There are n cars at various positions heading to the same destination along a one-lane road. The destination is target miles away.

You are given two integer arrays position and speed, both of length n, where position[i] is the starting mile of the i-th car and speed[i] is its speed in miles per hour.

A car can never pass another car ahead of it, but it can catch up and then drive at the same speed as the slower car right in front of it. Two cars are said to be in the same car fleet when they arrive at the same point. The faster car will slow down to match the slower car, and the distance between the two cars is ignored once they meet (they are assumed to occupy the same position).

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet. If a car catches up to a fleet exactly at target, it is still considered part of that fleet.

Return the number of car fleets that will arrive at the destination.

Constraints

n == position.length == speed.length
1 <= n <= 10^5
0 < target <= 10^6
0 <= position[i] < target
All the values of position are distinct.
0 < speed[i] <= 10^6

Examples

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

Complexity

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

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →