Car Fleet

Medium · Stack

You are given the length of a race track called target, and two lists of equal length describing cars driving toward that finish point on a single lane: position[i] is the starting distance of the i-th car from 0, and speed[i] is its constant speed. A faster car behind a slower one will catch up and then be forced to match the slower car's speed for the rest of the trip, so the two merge into a single fleet that arrives together; a car can never pass another. Return the number of distinct fleets that eventually reach or pass the target.

Examples

Input:  target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Why:    The cars starting at 10 and 8 merge into one fleet, the car at 5 and 3 merge into another, and the car at 0 travels alone, giving 3 fleets total.

Input:  target = 10, position = [3], speed = [3]
Output: 1
Why:    With only one car there can only be one fleet.

Input:  target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
Why:    The car at 0 is fastest and catches the others before target, so all three end up in a single fleet.

Constraints

1 <= position.length == speed.length <= 10^4, 0 < position[i] < target <= 10^6, 0 < speed[i] <= 10^6, all position values are distinct

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Car Fleet

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Car Fleet. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.