Problem overview
The method carFleet receives target, the distance in miles to the destination, and two arrays: position[i] is where car i starts, and speed[i] is its speed in miles per hour. All cars drive on a one-lane road and none can pass. A car that catches a slower one slows to its speed, and the two continue together as a fleet. A car alone is a fleet too, and a car that catches a fleet exactly at target counts as part of it. The method returns how many fleets arrive.
In the first example, target = 12, position = [10, 8, 0, 5, 3] and speed = [2, 4, 1, 1, 3]. The cars from miles 10 and 8 would both arrive after 1 hour, so the second catches the first exactly at the target: one fleet. The car from mile 3 catches the car from mile 5, and they arrive together after 7 hours: a second fleet. The car from mile 0 never catches anyone: a third. The answer is 3.
Approach: go from the front of the road and compare arrival times
Simulating every meeting between cars is messy. A simpler view: only the order of the cars on the road matters. If nothing slowed car i down, it would arrive after (target - position[i]) / speed[i] hours.
Visit the cars from the one closest to the target to the one farthest away. The closest car can never be blocked, so it leads the first fleet. For every other car, look at the fleet just ahead of it:
- If the car would arrive later than that fleet, it never catches up. It starts a new fleet.
- If it would arrive at the same time or earlier, it catches up at the latest at the target, and joins the fleet.
A fleet arrives when its lead car would arrive on its own, because that car was never slowed. So a stack of lead cars is enough. The fleet on top is the one just ahead of the next car, and it is also the one that arrives last, so comparing with the top alone is enough. The answer is the size of the stack. Here is the process on the first example:
order (car numbers): [0, 1, 3, 4, 2]
car 0 position=10 speed=2 alone arrives after 1.0 h: new fleet, fleets=[0]
car 1 position=8 speed=4 alone arrives after 1.0 h: joins fleet led by car 0, fleets=[0]
car 3 position=5 speed=1 alone arrives after 7.0 h: new fleet, fleets=[0, 3]
car 4 position=3 speed=3 alone arrives after 3.0 h: joins fleet led by car 3, fleets=[0, 3]
car 2 position=0 speed=1 alone arrives after 12.0 h: new fleet, fleets=[0, 3, 2]
On the third example, target = 100, position = [0, 2, 4] and speed = [4, 2, 1], the car at mile 4 arrives after 96 hours, and the other two would arrive sooner, after 49 and 25 hours, so both join it:
order (car numbers): [2, 1, 0]
car 2 position=4 speed=1 alone arrives after 96.0 h: new fleet, fleets=[2]
car 1 position=2 speed=2 alone arrives after 49.0 h: joins fleet led by car 2, fleets=[2]
car 0 position=0 speed=4 alone arrives after 25.0 h: joins fleet led by car 2, fleets=[2]
Sorting costs O(n log n) and the pass over the sorted cars does constant work per car.
Step by step
- Store the number of cars,
position.length, inn. - Create an
Integer[] orderof sizento hold car numbers. Sorting car numbers rather than positions keeps each position with its speed. - Fill it with a loop over
ifrom 0 ton - 1. - Set
order[i] = i. - Sort by position, closest to the target first, with
Arrays.sort(order, (a, b) -> position[b] - position[a]). The lambda gets two car numbers and returns a negative number whenamust come first, andposition[b] - position[a]is negative when carais closer to the target. - Create the stack
fleetsas aStack<Integer>. For each fleet it holds the number of the car that leads it. - Loop over
orderwith an enhancedforand anint car. - Start a new fleet when the stack is empty, or when the car arrives later than the fleet on top. That test is a call to the helper
arrivesLater(target, position, speed, car, fleets.peek()). The||stops at the firsttruepart, sopeek()only runs on a non-empty stack. - Push the car with
fleets.push(car). Cars behind it may still catch it, so it goes on top. If the car joins the fleet instead, nothing needs to be done. - Return
fleets.size()after the loop. - Write the helper
arrivesLater, returning aboolean, withtarget, the two arrays,carandleadas parameters. It answers whethercar, alone, would arrive strictly later thanlead. Strictly, because arriving at the same moment is one fleet. - Compare the times without dividing.
(target - position[car]) / speed[car] > (target - position[lead]) / speed[lead]is the same as(target - position[car]) * speed[lead] > (target - position[lead]) * speed[car], because speeds are positive. Equal times stay exactly equal. Cast the first factor of each product tolong.
The solution in Java
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
int n = position.length;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) {
order[i] = i;
}
Arrays.sort(order, (a, b) -> position[b] - position[a]);
Stack<Integer> fleets = new Stack<>();
for (int car : order) {
if (fleets.isEmpty() || arrivesLater(target, position, speed, car, fleets.peek())) {
fleets.push(car);
}
}
return fleets.size();
}
boolean arrivesLater(int target, int[] position, int[] speed, int car, int lead) {
return (long) (target - position[car]) * speed[lead] > (long) (target - position[lead]) * speed[car];
}
}
Java details:
Integer[], notint[].Arrays.sortwith a comparator only exists for arrays of objects. The array of boxedIntegervalues is the price of sorting by a custom rule.- The comparator. Subtracting two numbers works as a comparison only when the difference can't overflow. Here positions lie between 0 and 1,000,000, so it is safe.
- Why
long. Each product can reach about 1,000,000,000,000, and anintholds at most 2,147,483,647. Withtarget = 1000000,position = [7, 10]andspeed = [633474, 869424], the car at mile 7 arrives later and the correct answer is 2. Anintversion of the comparison wraps around and returns 1. - Where the cast goes.
(long) (target - position[car]) * speed[lead]converts the difference first, so the multiplication happens in 64 bits. Writing(long) ((target - position[car]) * speed[lead])multiplies asintfirst and casts the wrapped result. On the input above it producesfalsewhere the correct form producestrue. Stack.push,peekandsizeare all this solution needs.Dequeis the more modern choice, butStackworks fine here.
Complexity
Time: O(n log n). Sorting takes O(n log n). The loop does one comparison and at most one push per car, which is O(n).
Space: O(n). order and the stack each hold at most n entries.
Edge cases and common mistakes
- One car. It is a fleet by itself:
target = 10,position = [3],speed = [3]gives 1. - Arriving at the same moment. The comparison must be strict. In the first example, the cars from miles 10 and 8 both take exactly 1 hour, and they count as one fleet.
- Input in any order. Positions are not sorted in the input.
target = 10,position = [0, 4, 2],speed = [2, 1, 3]still gives 1. - Sorting only the positions. If
positionalone is sorted, the speeds no longer match. Sort car numbers, then look up both arrays through them. - Dividing the times. Comparing exact products avoids any question about rounding when two times are meant to be equal.
- A faster car in front. It never matters to the cars behind:
target = 10,position = [0, 1],speed = [5, 1]gives 1 (the back car catches up), whilespeed = [1, 5]gives 2.
Testing
target = 12,position = [10, 8, 0, 5, 3],speed = [2, 4, 1, 1, 3]gives 3.target = 10,position = [3],speed = [3]gives 1.target = 100,position = [0, 2, 4],speed = [4, 2, 1]gives 1.target = 10,position = [0, 4, 2],speed = [2, 1, 3]gives 1.target = 10,position = [0, 1],speed = [1, 5]gives 2.target = 1000000,position = [7, 10],speed = [633474, 869424]gives 2.
