Start learning free

LESSON 467 OF 671 · STACK

Car Fleet

Practice O(n log n)

You get a number target and two arrays, position and speed. Car i starts at mile position[i]. It drives at speed[i] miles per hour.

All the cars drive on one lane toward mile target. Return how many fleets arrive at target.

A car can't pass another car. When it catches up with a slower car, it stays behind it. Then it goes on at that car's speed. Cars that drive on together like this are a fleet. A car on its own is a fleet too. Catching up exactly at target also counts as joining.

 

Example 1:

Input: target = 20, position = [14, 2, 8, 10], speed = [3, 6, 2, 1]
Output: 2
Explanation:
The car from mile 14 arrives after 2 hours.
No car catches it. It is one fleet.
The car from mile 10 is the slowest. It needs 10 hours.
The cars from miles 8 and 2 catch up with it at mile 12.
These three arrive together. They are the second fleet.

Example 2:

Input: target = 9, position = [3, 6], speed = [2, 1]
Output: 1
Explanation: Both cars need 3 hours.
The car from mile 3 catches the other one exactly at the target.
So they count as one fleet.

Example 3:

Input: target = 10, position = [0, 4, 7], speed = [1, 2, 3]
Output: 3
Explanation: Each car is faster than the cars behind it.
No car ever catches another.
So there are three fleets.

 

Constraints:

  • 1 to 100,000 cars.
  • position and speed have one value per car.
  • target is from 1 to 1,000,000.
  • Each car starts from mile 0 to mile target - 1.
  • No two cars start at the same mile.
  • Each speed is from 1 to 1,000,000.

Note:

Your algorithm should run in O(n log n) time and use O(n) extra space.



Only the order of the cars on the road matters, so visit them from the one closest to the target to the one farthest from it. If nothing slowed it down, car i would arrive after (target - position[i]) / speed[i] hours. A car that would arrive no later than the fleet just ahead of it catches up with that fleet, at the latest at the target, and joins it. A car that would arrive later never catches up: it starts a new fleet, which the cars behind it may join.

Keep the fleets found so far on a stack. A fleet arrives when the car that leads it would arrive on its own, since that car was never slowed down. The fleet just ahead of the next car is always the one on top of the stack, and it is also the one that arrives last: compare the car with it only. A car that would arrive later starts a new fleet and goes on top; otherwise it joins the top fleet. The answer is the size of the stack.

The times are fractions. Compare them exactly, without dividing: since the speeds are positive, (target - p1) / s1 > (target - p2) / s2 is the same as (target - p1) * s2 > (target - p2) * s1. These products can reach 1012, more than a 32-bit integer holds: where integers are 32 bits, compute them with 64-bit integers. A Python integer, or a JavaScript or TypeScript number (exact for whole numbers below 253), holds them as it is.

Sorting the cars by position takes O(n log n) time. The pass over the sorted cars does a constant amount of work for each car, so sorting is the larger part. The sorted order and the stack hold at most n cars each: O(n) extra space.
STEP 1 OF 12
    Ctrl + Enter to check