How to Solve Car Fleet

The Car Fleet problem requires determining how many car fleets will reach the target, using the stack-based state management approach. This can be achieved by calculating each car's time to reach the target and using a stack to manage the fleet's formation as cars catch up to each other. The correct solution involves analyzing how cars group together based on their speeds and positions.

Problem Statement

You are given two arrays, position and speed, representing the starting mile and speed of each car. You also know the target mile the cars need to reach. The cars travel towards the target, but they can’t pass each other. If a car catches up to another, they form a fleet and travel together at the speed of the slower car in the fleet.

Your task is to determine the number of car fleets that will reach the target. A fleet is a group of cars that will arrive at the target at the same time due to their speeds and the fact that they can’t overtake each other. Return the number of fleets at the target.

Examples

Example 1

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

Output: 3

Example 2

Input: target = 10, position = [3], speed = [3]

Output: 1

Example 3

Input: target = 100, position = [0,2,4], speed = [4,2,1]

Output: 1

Constraints

• n == position.length == speed.length
• 1 <= n <= 105
• 0 < target <= 106
• 0 <= position[i] < target
• All the values of position are unique.
• 0 < speed[i] <= 106

Solution Approach

Sort the Cars by Position

First, sort the cars based on their starting positions in decreasing order. This ensures that we process the cars in the order they are encountered as we simulate their movement toward the target.

Calculate Time to Reach the Target

For each car, calculate the time it will take to reach the target using the formula time = (target - position[i]) / speed[i]. This gives us the time required for each car to reach the target.

Track Fleets with a Stack

Use a stack to track the car fleets. For each car, check if it can catch up with the car in front of it (i.e., if its time to reach the target is greater than the car in front). If it cannot catch up, it's a new fleet. If it can catch up, it joins the fleet at the front.

Complexity Analysis

The time complexity of this solution is O(n log n) due to the sorting step, where n is the number of cars. The space complexity is O(n) because we store the times and fleets in a stack, where n is the number of cars.

What Interviewers Usually Probe

• Look for understanding of stack-based state management and how it can be used to simulate the formation of car fleets.
• Assess whether the candidate can explain the key concept of cars catching up and joining fleets without overtaking.
• Evaluate the candidate’s ability to relate sorting and time calculations to the problem's logic, ensuring efficient fleet tracking.

Common Pitfalls or Variants

Common pitfalls

• Failing to sort the cars correctly, which would lead to incorrect fleet grouping.
• Misunderstanding the concept of fleet formation and incorrectly counting cars that are part of the same fleet.
• Not accounting for cars that reach the target at the same time, which would result in overcounting fleets.

Follow-up variants

• What if cars can overtake each other? This would change the approach as fleet formation rules would be different.
• What if the target is at the maximum boundary? This tests whether the solution can handle large input sizes efficiently.
• What if some cars start at the same position? This would require handling cases where multiple cars start from the same point but have different speeds.

How GhostInterview Helps

• GhostInterview offers targeted practice for stack-based problems like this, providing a clear and structured approach to managing car fleets.
• With examples and step-by-step guidance, GhostInterview ensures that candidates understand fleet formation and time calculations before tackling the problem.
• GhostInterview highlights common pitfalls such as incorrect sorting or missing fleet groupings, helping candidates prepare thoroughly for real interviews.

Topic Pages

• Array
• Stack
• Sorting
• Monotonic Stack

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the key pattern for solving the Car Fleet problem?

The Car Fleet problem is best solved using stack-based state management, where cars are processed in the order of their starting positions, and fleets are formed based on their times to reach the target.

How do I calculate the time for each car to reach the target?

To calculate the time for each car to reach the target, use the formula (target - position[i]) / speed[i], where position[i] is the car’s starting point, and speed[i] is its speed.

What happens if two cars reach the target at the same time?

If two cars reach the target at the same time, they form a fleet and are counted as one, meaning you should only count the number of distinct fleets formed.

Can I solve this problem with a brute force approach?

A brute force approach could be inefficient as it would require simulating each car's movement, potentially leading to a time complexity greater than O(n log n). Sorting and stack management offer a more optimal solution.

What is the time complexity of the Car Fleet problem?

The time complexity of the solution is O(n log n), where n is the number of cars, because sorting is the most computationally expensive step.