#853

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Car Fleet

The Car Fleet problem asks how many car fleets will reach a target given their starting positions and speeds, considering that cars can’t overtake each other.

array stack sorting monotonic stack

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        idx = sorted(range(len(position)), key=lambda i: position[i])
        ans = pre = 0
        for i in idx[::-1]:
            t = (target - position[i]) / speed[i]
            if t > pre:
                ans += 1
                pre = t
        return ans

Continue Practicing

#769 max chunks to make sorted #768 max chunks to make sorted ii #975 odd even jump