Car Fleet

The problem

Cars drive along a one-lane road toward the position target. The lists position and speed give, for each car, where it starts and how fast it drives. A car cannot pass the car in front of it: when it catches up, it slows down to that car's speed and follows it from then on. Cars that arrive together form a fleet, and a car that arrives by itself is a fleet of one. A car that catches up exactly at the target still counts as part of that fleet. Return the number of fleets that arrive at the target.

What to write

function solve(target: number, position: number[], speed: number[]): number

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

Output
3

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

Output
1

Constraints

Positions are distinct, below target, and speeds are positive.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Cars cannot pass, so what happens to a car depends only on the cars in front of it, never on those behind. Notice that the lists are not in road order: the first car listed is not always the one nearest the target.

2. Hint 2: Ask a smaller question

   Take two cars. Driving alone, the one in front would reach the target at time 5 and the one behind at time 3. Do they arrive together? Now swap the two times. What single comparison decides it?

3. Hint 3: Name the pattern

   A car's fate is decided by the fleet directly ahead. Sort the cars by position and read from the front: each new fleet arrives later than the one before, and a car that would not arrive later is absorbed. The fleets' arrival times form a monotonic stack: each time pushed is larger than the one under it. Read the lesson on monotonic stack.

4. Hint 4: State the invariant

   Going from the front car back, the top of the stack is the arrival time of the fleet directly ahead. It is the largest time seen so far. A car joins that fleet exactly when its own time alone is not larger.

5. Hint 5: Sketch the pseudocode

   Pair each position with its speed and sort the pairs by position, largest first. Start an empty stack. For each car: time = (target minus position) ÷ speed. If the stack is empty or time is greater than its top, push time. Return the size of the stack.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Sort from closest to target to farthest. Push a car's arrival time on a stack only if it exceeds the time on top; the size of the stack is the answer.

The slow way

Simulate the drive: move every car forward a little at a time, slow down any car that reaches the one in front, and count the groups at the target. It can be made to work, but the number of rounds depends on the distances and speeds, and cars that meet between two rounds are easy to miss.

The insight

You do not need to follow the cars along the road. Each car has one number: the time it would need to reach the target alone. It catches the fleet in front exactly when that number is not larger than the fleet's arrival time. Stack up the fleets' times and they only grow, a monotonic stack, and only the top is ever compared.

Step by step

1. Line the cars up from nearest the target to farthest. A car is only ever held up by cars in front of it. In this order, every car that could block the current one has already been handled.
2. Keep a stack of arrival times, one for each fleet found so far. Each time on the stack belongs to one fleet, and the top is the fleet directly ahead of the next car. The stack starts empty, so the front car always starts a fleet.
3. Work out when this car would arrive on an empty road. It is the distance to the target divided by the speed. This is the earliest the car could ever arrive: a slower fleet in front can only delay it.
4. A car that would arrive later than the fleet on top leads a new fleet. It never catches up, so it arrives separately: its time is pushed, and the cars behind are compared with that. A car with an earlier or equal time catches the fleet and pushes nothing.
5. Each time on the stack is one fleet that arrives. A time was pushed once for each car that could not catch the fleet ahead of it, and those cars are exactly the leaders of the fleets that arrive.

The same numbered steps are the comments in each solution.

function solve(target, position, speed) {
  // 1. Line the cars up from nearest the target to farthest
  const cars = position
    .map((p, i) => [p, speed[i]])
    .sort((a, b) => b[0] - a[0]);
  // 2. Keep a stack of arrival times, one for each fleet found so far
  const fleets = [];
  for (const [carPosition, carSpeed] of cars) {
    // 3. Work out when this car would arrive on an empty road
    const arrival = (target - carPosition) / carSpeed;
    // 4. A car that would arrive later than the fleet on top leads a new fleet
    // at(-1) is the top of the stack: the fleet directly ahead of this car.
    if (!fleets.length || arrival > fleets.at(-1)) fleets.push(arrival);
  }
  // 5. Each time on the stack is one fleet that arrives
  return fleets.length;
}

function solve(target: number, position: number[], speed: number[]): number {
  // 1. Line the cars up from nearest the target to farthest
  const cars = position
    .map((p, i) => [p, speed[i]])
    .sort((a, b) => b[0] - a[0]);
  // 2. Keep a stack of arrival times, one for each fleet found so far
  const fleets: number[] = [];
  for (const [carPosition, carSpeed] of cars) {
    // 3. Work out when this car would arrive on an empty road
    const arrival = (target - carPosition) / carSpeed;
    // 4. A car that would arrive later than the fleet on top leads a new fleet
    // at(-1) is the top of the stack: the fleet directly ahead of this car.
    if (!fleets.length || arrival > fleets.at(-1)!) fleets.push(arrival);
  }
  // 5. Each time on the stack is one fleet that arrives
  return fleets.length;
}

def solve(target, position, speed):
    # 1. Line the cars up from nearest the target to farthest
    cars = sorted(zip(position, speed), reverse=True)
    # 2. Keep a stack of arrival times, one for each fleet found so far
    fleets = []
    for car_position, car_speed in cars:
        # 3. Work out when this car would arrive on an empty road
        arrival = (target - car_position) / car_speed
        # 4. A car that would arrive later than the fleet on top leads a new fleet
        # fleets[-1] is the top of the stack: the fleet directly ahead of this car.
        if not fleets or arrival > fleets[-1]:
            fleets.append(arrival)
    # 5. Each time on the stack is one fleet that arrives
    return len(fleets)

Example 1, traced

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

Output
3

Why it works

Going from the front car back, the top of the stack is the arrival time of the fleet directly ahead. A car that would arrive no later than that must run into the fleet before or at the target, and it arrives with the fleet. A car that would arrive later never reaches the fleet, so it leads a new one.

Time and space

Time O(n log n), extra space O(n). Sorting the n cars by position takes about n log n steps, and the pass after it does a constant amount of work for each car: O(n log n) time in total. The sorted list and the stack hold at most n entries each: O(n) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Sort first, with the car nearest the target in front. In the input's own order, example 1 counts 2 fleets instead of 3, because the cars at 5 and 3 are compared with the car at 0 behind them.
• A car whose time equals that of the fleet ahead joins it. Counting an equal time as a new fleet gives 4 for example 1, where the cars at 10 and 8 both arrive at time 1.
• Push a time only when a new fleet starts. A car that joined a fleet arrives with the fleet, so the cars behind must be compared with the fleet's time, not with that car's own shorter time.

Pattern

Monotonic stack. Builds on Daily Temperatures.

Keep going