Car Fleet

Car Fleet is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Monotonic Stack subpattern.

Problem statement

You are given a destination point in target and a set of cars traveling toward it. The ith car starts at position position[i] and travels at constant speed speed[i]; the two arrays describe the same cars, so their lengths are equal.

Cars move in the same direction and may not pass one another. If a car behind catches a slower car ahead before reaching target, it joins that car's fleet and then travels at the slower fleet speed. A fleet is a group of cars that reaches target together; a car that never catches another remains a fleet by itself.

Return the total number of fleets that arrive at target.

Example 1:

Input: target = 20, position = [3,8,14,17], speed = [5,3,2,1] Output: 2 Explanation: The cars at positions 17 and 14 reach the destination at the same time and form one fleet. The car at position 8 forms another fleet, while the car at position 3 catches that fleet before the destination, giving two fleets total.

Example 2:

Input: target = 30, position = [4,10,18,25], speed = [6,4,3,2] Output: 3 Explanation: The car at position 25 arrives in 2.5 time units, and the car at position 18 arrives in 4 time units, so they remain separate. The car at position 10 arrives in 5 time units, while the car at position 4 catches it, producing one additional fleet and three total.

Example 3:

Input: target = 25, position = [2,7,16,21], speed = [2,5,2,4] Output: 3 Explanation: The car at position 21 forms the first fleet. The car at position 7 catches the car at position 16, forming the second fleet, while the car at position 2 is too slow to catch that fleet and remains separate.

Constraints:

- 1 <= target <= 10^6 - 1 <= position.length = speed.length <= 10^5 - 0 <= position[i] < target - 1 <= speed[i] <= 10^6 - All values in position are distinct. - Each position[i] and speed[i] is an integer. - position[i] and speed[i] belong to the same car.

Topics and companies

Topics: Stack, Sorting, Greedy, Array.

How to practise Car Fleet on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n log n), due to sorting the cars by starting position. time and O(n) for the sorted car list and fleet arrival times. space.

Open Car Fleet in the code editor, or read the Car Fleet editorial for a worked solution with its approach and complexity analysis.

Where Car Fleet sits in the DSA pattern sheet

Problems related to Car Fleet

Other problems that use the same Monotonic Stack and Stack Patterns techniques:

Preparing this workspace.