Problem Description

You have n cars on a straight road, each starting at different positions and traveling toward a destination at mile target.

Given:

• position[i]: the starting mile of car i
• speed[i]: the speed of car i in miles per hour

Key Rules:

1. Cars travel in the same direction toward the target
2. A faster car cannot pass a slower car ahead of it
3. When a faster car catches up to a slower car, they form a car fleet and travel together at the slower car's speed
4. Multiple cars traveling together as a group count as one fleet
5. If cars meet exactly at the target, they still count as one fleet

Goal: Count how many separate car fleets will arrive at the destination.

Example Visualization: If car A is behind car B but moving faster:

• If A catches up to B before the target → they form 1 fleet
• If A doesn't catch up to B before the target → they remain 2 separate fleets

The solution works by:

1. Sorting cars by their starting positions (closest to target first)
2. Calculating each car's time to reach the target: time = (target - position) / speed
3. Starting from the car closest to target, checking if cars behind it will catch up
4. If a car takes longer to reach the target than the car ahead, it forms a new fleet
5. If a car would reach faster but gets blocked, it joins the existing fleet

Intuition

The key insight is to think about this problem from the destination backwards. Instead of tracking how cars move forward and merge, we can determine which cars will form fleets by calculating when each car would arrive at the target if it traveled unimpeded.

Why work backwards from the target?

Consider the car closest to the target. This car will never be blocked by anyone - it sets the "pace" for any cars behind it that might catch up. Any car behind it that would theoretically arrive earlier (has a shorter arrival time) must catch up and slow down to match its speed, forming a fleet.

The arrival time concept:

For each car, we calculate: arrival_time = (target - position) / speed

This tells us when the car would reach the target if traveling alone.

The blocking principle:

Starting from the car closest to the target:

• If a car behind has a shorter arrival time, it means it's fast enough to catch up → it joins the current fleet
• If a car behind has a longer arrival time, it means it's too slow to catch up → it forms a new, separate fleet

Why this works:

Imagine cars A, B, C positioned in that order (A closest to target):

• If B would arrive after A (time_B > time_A), B can never catch A → separate fleets
• If B would arrive before A (time_B < time_A), B catches A and they travel together
• Now if C would arrive even earlier than B, C still gets stuck behind the A-B fleet
• But if C's arrival time is later than A's, C forms its own fleet

By processing cars from closest to farthest from the target, we can simply track the "blocking time" - the longest arrival time seen so far. Any car with a longer arrival time than this blocking time must form a new fleet.

Learn more about Stack, Sorting and Monotonic Stack patterns.

Solution Approach

Let's walk through the implementation step by step:

Step 1: Sort cars by position

idx = sorted(range(len(position)), key=lambda i: position[i])

We create an index array sorted by car positions. This gives us the order of cars from closest to farthest from the starting point. We'll process them in reverse order (farthest to closest to start = closest to farthest from target).

Step 2: Initialize tracking variables

ans = pre = 0

• ans: counts the number of fleets
• pre: tracks the longest arrival time seen so far (the "blocking time")

Step 3: Process cars from closest to target

for i in idx[::-1]:
    t = (target - position[i]) / speed[i]

We iterate through cars in reverse order (idx[::-1]), starting with the car closest to the target. For each car, we calculate its arrival time t.

Step 4: Determine if a new fleet forms

if t > pre:
    ans += 1
    pre = t

The core logic:

• If current car's arrival time t is greater than pre (the previous blocking time), this car cannot catch up to any fleet ahead
• This car forms a new fleet, so we increment ans
• Update pre to this new, longer arrival time as it becomes the new blocking time for cars behind

Why this works:

• Cars with arrival time ≤ pre will catch up to the fleet ahead and join it
• Cars with arrival time > pre are too slow to catch up and form their own fleet
• By processing from target backwards, we ensure each car only needs to check against one blocking time

Example walkthrough:

target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Sorted by position: [0,3,5,8,10] with speeds [1,3,1,4,2]
Process in reverse: 
- Car at 10: time = (12-10)/2 = 1, forms fleet 1, pre = 1
- Car at 8: time = (12-8)/4 = 1, equals pre, joins fleet 1
- Car at 5: time = (12-5)/1 = 7, > pre, forms fleet 2, pre = 7
- Car at 3: time = (12-3)/3 = 3, < pre, joins fleet 2
- Car at 0: time = (12-0)/1 = 12, > pre, forms fleet 3
Result: 3 fleets

Example Walkthrough

Let's walk through a concrete example to see how the solution works:

Input:

• target = 10
• position = [6, 2, 0]
• speed = [3, 2, 1]

Step 1: Calculate arrival times and sort by position

First, let's visualize the cars on the road:

Start:  0---2-------6----------10 (target)
        C   B       A

Calculate when each car would reach the target if traveling alone:

• Car A (pos=6, speed=3): time = (10-6)/3 = 1.33 hours
• Car B (pos=2, speed=2): time = (10-2)/2 = 4 hours
• Car C (pos=0, speed=1): time = (10-0)/1 = 10 hours

Sort cars by position to get processing order: A, B, C

Step 2: Process cars from closest to target (A → B → C)

Initialize: fleets = 0, blocking_time = 0

Process Car A (closest to target):

• Arrival time: 1.33 hours
• Is 1.33 > blocking_time (0)? YES
• Car A forms a new fleet → fleets = 1
• Update blocking_time = 1.33

Process Car B:

• Arrival time: 4 hours
• Is 4 > blocking_time (1.33)? YES
• Car B is too slow to catch Car A, forms new fleet → fleets = 2
• Update blocking_time = 4

Process Car C:

• Arrival time: 10 hours
• Is 10 > blocking_time (4)? YES
• Car C is too slow to catch Car B, forms new fleet → fleets = 3

Result: 3 separate fleets

Verification: Let's verify by thinking forward:

• Car A reaches target at 1.33 hours alone
• Car B would need 4 hours, can't catch A
• Car C would need 10 hours, can't catch B

Indeed, all three cars arrive separately!

Alternative scenario: What if Car B was faster? If Car B had speed=5 instead:

• Car B's time = (10-2)/5 = 1.6 hours
• Still > 1.33, so B still can't catch A
• Result: Still 3 fleets

But if Car B had speed=8:

• Car B's time = (10-2)/8 = 1 hour
• 1 < 1.33 (blocking_time), so B would catch A!
• B joins A's fleet, traveling at A's speed
• Result: Would be 2 fleets (A+B together, C alone)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the number of cars.

• The sorted() function creates a sorted list of indices based on positions, which takes O(n log n) time.
• The subsequent for loop iterates through all n indices once, performing constant time operations for each car (calculating time t and comparisons), which takes O(n) time.
• Overall time complexity is dominated by the sorting step: O(n log n) + O(n) = O(n log n).

Space Complexity: O(n) where n is the number of cars.

• The idx variable stores a list of n indices, requiring O(n) space.
• The sorted() function internally uses additional space for sorting (typically O(n) for Python's Timsort algorithm).
• Other variables (ans, pre, t, i) use constant space O(1).
• Total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Sorting Cars in Wrong Direction

A common mistake is sorting cars by position but processing them in the wrong order. Many developers instinctively process from the car furthest from target to closest, which breaks the logic.

Wrong approach:

for index in sorted_indices:  # Processing from furthest to closest to target
    time_to_target = (target - position[index]) / speed[index]
    # This doesn't work because we need to check if cars can catch up to those ahead

Solution: Always process from closest to target first (reverse the sorted indices):

for index in sorted_indices[::-1]:  # Correct: closest to target first
    time_to_target = (target - position[index]) / speed[index]

2. Using Wrong Comparison Operator

Another frequent error is using >= instead of > when checking if a new fleet forms.

Wrong approach:

if time_to_target >= previous_time:  # Wrong! This creates too many fleets
    fleet_count += 1
    previous_time = time_to_target

Solution: Use strict greater than (>). Cars arriving at the same time form one fleet:

if time_to_target > previous_time:  # Correct: only form new fleet if strictly slower
    fleet_count += 1
    previous_time = time_to_target

3. Forgetting Edge Cases

Not handling edge cases like empty arrays or single car scenarios.

Wrong approach:

def carFleet(self, target, position, speed):
    sorted_indices = sorted(range(len(position)), key=lambda i: position[i])
    # Crashes if position is empty

Solution: Add edge case handling:

def carFleet(self, target, position, speed):
    if not position:
        return 0
    if len(position) == 1:
        return 1
    # Continue with main logic

4. Integer Division Instead of Float Division

In Python 2 or when dealing with integer inputs, using integer division can cause incorrect time calculations.

Wrong approach (Python 2 style):

time_to_target = (target - position[index]) // speed[index]  # Integer division loses precision

Solution: Ensure float division:

time_to_target = (target - position[index]) / speed[index]  # Float division
# Or explicitly: float(target - position[index]) / speed[index]

5. Misunderstanding the Fleet Formation Logic

Some developers try to track which cars belong to which fleet explicitly, making the solution unnecessarily complex.

Overcomplicated approach:

fleets = []
for car in cars:
    joined = False
    for fleet in fleets:
        if car_can_catch_up(car, fleet):
            fleet.append(car)
            joined = True
            break
    if not joined:
        fleets.append([car])

Solution: Just count fleets by tracking the "blocking time" - much simpler and more efficient:

if time_to_target > previous_time:
    fleet_count += 1
    previous_time = time_to_target