Car Fleet — Medium Coding Interview Question

There are n cars going to the same destination along a one-lane road, target miles away. Given position and speed arrays, a car cannot pass the car ahead of it — it merges into a fleet at that car's speed instead. Return the number of car fleets that will arrive at the destination.

Example

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]

Output: 3

Constraints

• n == position.length == speed.length
• 1 ≤ n ≤ 10⁵
• 0 < target ≤ 10⁶
• 0 ≤ position[i] < target (all unique)
• 0 < speed[i] ≤ 10⁶

Topics & Companies

Topics: stack, sorting, arrays

Asked by: Google, Amazon

Optimal Solution Complexity

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

Practice more

• All DSA Problems
• DSA Patterns