Car Fleet

Q: What is the time complexity of Car Fleet?

Sorting by position takes O(n log n) and the pass with a stack takes O(n) , so the total is O(n log n) time and O(n) memory. Checking every car against every car ahead takes O(n²) .

Q: How do you compare arrival times without floating point?

An arrival time is dist / speed . Since speeds are positive, d1 / s1 > d2 / s2 holds exactly when d1 × s2 > d2 × s1 . Both sides are integers up to 10^12 , so compute them in a 64-bit type and the comparison is exact, with no rounding to reason about.

MediumStack Sorting

+10

Cars drive along a one-lane road toward mile target. Car i starts at mile position[i] and drives at speed[i] miles per hour. No car can pass another: a car that catches up with a slower one stays right behind it, and from then on the two move together at the slower speed as one fleet.

A single car is a fleet too, and a car that reaches a fleet exactly at the destination joins it. Return the number of fleets that arrive at the destination.

Function

carFleet(target: integer, position: integer-array, speed: integer-array) → integer

targetinteger: the mile where every car is heading
positioninteger-array: the starting mile of each car
speedinteger-array: the speed of each car, in miles per hour
Returnsinteger: the number of fleets that reach the destination

Constraints

n == position.length == speed.length
1 ≤ n ≤ 10⁴
1 ≤ target ≤ 10⁶
0 ≤ position[i] < target
1 ≤ speed[i] ≤ 10⁶
All positions are different.

Examples

Input: target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
Output: 2
Explanation: Alone, the cars at miles 17, 14, 8 and 2 need 3, 2, 3 and 3 hours, so 14 catches 17 and the other two reach them at mile 20. The car at 0 needs 10 hours and arrives alone.

Input: target = 9position = [0, 4, 7]speed = [1, 2, 3]
Output: 3
Explanation: The cars at miles 7, 4 and 0 need 2/3, 5/2 and 9 hours. Each would arrive after the car ahead of it, so nobody catches anybody: 3 fleets.

Follow-up

The positions are integers below target. Can you count the fleets in O(n + target) time, without a comparison sort?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

On one lane the cars never change order, and what decides everything is when each car would arrive alone: (target - position[i]) / speed[i]. Visit the cars from the one closest to the destination backward. A car starts a new fleet only when it would arrive strictly later than the fleet ahead of it.

Check every car ahead

Correct, but does not finish on the largest tests

Intuition

A car leads a fleet exactly when every car ahead of it would arrive strictly earlier alone. If some car ahead would arrive no earlier, your car catches it, or its fleet, by the destination. If all arrive earlier, nothing ahead can hold it up, because a fleet arrives at the latest lone time among its cars. Count the leading cars, comparing times exactly by cross-multiplying.

Each car scans all n cars: 10^8 checks for n = 10^4.

Algorithm

Set fleets = 0.
For each car i, look at every car j with position[j] > position[i].
If some j has (target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j], car i is caught: skip it.
Otherwise car i leads a fleet: add 1 to fleets.
Return fleets.

def carFleet(target, position, speed):
    n = len(position)
    fleets = 0
    for i in range(n):
        dist = target - position[i]
        caught = False
        for j in range(n):
            # Car j is ahead and would not arrive before car i: car i catches it.
            # (target - position[j]) / speed[j] >= dist / speed[i], without division.
            if position[j] > position[i] and (target - position[j]) * speed[i] >= dist * speed[j]:
                caught = True
                break
        if not caught:
            fleets += 1
    return fleets

Sort by position and stack the fleets

Intuition

Sorted by position, closest to the destination first, the cars ahead of the current one are exactly those already seen, already in fleets. Keep the fleets on a stack, each stored as the distance and speed of its front car, which sets the fleet's arrival time.

Only the top matters. Each push arrives strictly later than the fleet below it, so the times rise from bottom to top, and later than the top means later than every car ahead.

Example 1 in order is the cars at 17, 14, 8, 2 and 0, with distance over speed 3/1, 6/3, 12/4, 18/6, 20/2. Push (3, 1). The car at 14 joins, since 6 × 1 > 3 × 3 is false. The car at 8 ties, 12 × 1 = 3 × 4, and joins, and so does the car at 2. For the car at 0, 20 × 1 > 3 × 2: push.

Algorithm

Sort the car indexes by position, largest first.
Start with an empty stack of fleets.
For each car, compute dist = target - position[i].
If the stack is empty or dist × topSpeed > topDist × speed[i], push (dist, speed[i]); otherwise the car joins the top fleet.
Return the size of the stack.

def carFleet(target, position, speed):
    # Visit the cars from the one closest to the target backward.
    order = sorted(range(len(position)), key=lambda i: position[i], reverse=True)
    # One entry per fleet: (distance, speed) of the car at its front, which sets its arrival time.
    stack = []
    for i in order:
        dist, spd = target - position[i], speed[i]
        # dist / spd > top_dist / top_spd, compared without division:
        # this car arrives after the fleet ahead, so it never catches it.
        if not stack or dist * stack[-1][1] > stack[-1][0] * spd:
            stack.append((dist, spd))
    return len(stack)

Pitfalls and edge cases

Counting an exact tie as a new fleet. The cars at miles 8 and 2 in example 1 meet the fleet at mile 20 and join it. Push only when the time is strictly later.
Overflow in the cross product. 10^6 × 10^6 = 10^12 does not fit in 32 bits: in Java, C, C++, C# and Rust, widen to 64 bits before multiplying; in R, use doubles.
Sorting the wrong way. Starting from the car farthest from the destination compares each car with the cars behind it, which can never block it.
Sorting position on its own. Sort indexes, or (position, speed) pairs, so each speed stays with its car.

Frequently asked questions3

What is the time complexity of Car Fleet?

Sorting by position takes O(n log n) and the pass with a stack takes O(n), so the total is O(n log n) time and O(n) memory. Checking every car against every car ahead takes O(n²).

Why does Car Fleet use a stack?

Visiting the cars from the front, each new car only has to be compared with the fleet directly ahead, the one formed last. A stack keeps that fleet on top. Since only the top is read, two variables work too; the stack also leaves you with the fleets themselves.

How do you compare arrival times without floating point?

An arrival time is dist / speed. Since speeds are positive, d1 / s1 > d2 / s2 holds exactly when d1 × s2 > d2 × s1. Both sides are integers up to 10^12, so compute them in a 64-bit type and the comparison is exact, with no rounding to reason about.

def carFleet(target, position, speed):
    # Write code here

Test #1

Test #2

Test #3

Arguments

target = 20
position = [14, 2, 8, 17, 0]
speed = [3, 6, 4, 1, 2]

Expected Output