Problem overview
Several cars drive on a one-lane road toward the same destination, target miles from the start. Car i starts at mile position[i] and drives at speed[i] miles per hour. A car can't pass the car ahead of it. When it catches up with a slower car, it slows down and the two drive on together, at the speed of the car in front. A group of cars driving together is a fleet, and a car alone is a fleet too. A car that reaches a fleet exactly at target belongs to it. The method carFleet returns how many fleets arrive at target.
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 5 would take 7 hours, and the car from mile 3 only 3, so they meet and drive on together at speed 1: a second fleet. The car from mile 0 would need 12 hours and never catches anyone: a third. The answer is 3. In the third example, target = 100, position = [0, 2, 4] and speed = [4, 2, 1], each car catches up with the one ahead, and all three arrive together as one fleet.
The statement asks for O(n log n) time and O(n) extra space.
Approach: sort by position, then compare arrival times
Only the order of the cars on the road matters. 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. Call that its own time.
The car closest to the target can never be blocked, so it leads a fleet. For each car after that, look at the fleet just ahead of it. If the car's own time is no more than that fleet's time, the car catches the fleet, at the latest at the target, and joins it. If its own time is larger, it never catches up and starts a new fleet, which the cars behind it may still join.
A fleet arrives when the car that leads it would arrive on its own, because the lead car is never slowed down. So a stack of the leading cars is enough: the top is the fleet just ahead of the next car. The answer is the stack's size.
For the first example, the cars sorted from the target backward, with their own times, are:
car 0 position 10 time 1.0
car 1 position 8 time 1.0
car 3 position 5 time 7.0
car 4 position 3 time 3.0
car 2 position 0 time 12.0
Car 0 starts the first fleet. Car 1 takes 1.0 hour, which is not more than 1.0, so it joins. Car 3 takes 7.0, more than the top's 1.0, so it starts the second fleet. Car 4 takes 3.0, which is not more than 7.0, so it joins that fleet. Car 2 takes 12.0, more than 7.0, so it starts the third. The program prints 3.
Step by step
- Sort the car numbers.
orderisposition.indices.sorted { position[$0] > position[$1] }. Sorting the car numbers, not the positions, keeps each position tied to its speed: carorder[k]starts atposition[order[k]]and drives atspeed[order[k]]. The closure puts the larger position first, so the car closest to the target comes first. - Create the stack.
fleetsis an empty[Int]. For each fleet it holds the number of the car that leads it, and its last element is the top. - Loop over
orderwith the variablecar. - Decide if the car starts a new fleet. This happens when the stack is empty, or when the car would arrive later than the fleet on top,
fleets.last!. A helper,arrivesLater, answers that. - Push it with
fleets.append(car). A car that doesn't start a fleet joins the one ahead, and there is nothing to do. - Return
fleets.countafter the loop. - Write the helper.
arrivesLatertakes the target, both arrays, the car and the lead car, and returns aBool. - Compare the times without dividing. The car arrives later when
(target - position[car]) / speed[car]is greater than(target - position[lead]) / speed[lead]. Multiplying both sides by the two speeds, which are positive, gives(target - position[car]) * speed[lead] > (target - position[lead]) * speed[car], with no fractions. The comparison is strict: a car that arrives at the same moment catches up exactly at the target, and that still counts as one fleet.
The solution in Swift
class Solution {
func carFleet(_ target: Int, _ position: [Int], _ speed: [Int]) -> Int {
let order = position.indices.sorted { position[$0] > position[$1] }
var fleets = [Int]()
for car in order {
if fleets.isEmpty || arrivesLater(target, position, speed, car, fleets.last!) {
fleets.append(car)
}
}
return fleets.count
}
func arrivesLater(_ target: Int, _ position: [Int], _ speed: [Int], _ car: Int, _ lead: Int) -> Bool {
return (target - position[car]) * speed[lead] > (target - position[lead]) * speed[car]
}
}
The Swift details worth knowing:
position.indicesis the range0..<position.count. Callingsortedon it gives a new[Int]of car numbers, ordered by the closure.$0and$1are the two numbers being compared, and the closure says whether the first should come before the second.fleets.last!.lastis an optional, because an array can be empty. The!unwraps it. It is safe because||stops at the first true part: whenfleets.isEmptyis true,fleets.last!is never evaluated.- The underscores in the parameter lists mean the caller writes no labels, so the call reads
arrivesLater(target, position, speed, car, fleets.last!). - Why multiply and not divide. Integer division in Swift truncates, so
7 / 2and6 / 2are both 3, although the times differ. Converting toDoublewould work for most inputs, but comparing two quotients for equality is risky. The cross-multiplied form uses only integers, so equal times stay exactly equal. - Overflow. The products reach about a trillion (10^12), since a distance can be near a million and a speed too. Swift's
Intis 64 bits, so they fit. In a 32-bit integer they would not: forInt32values,1_000_000 * 1_000_000overflows, and Swift stops the program with a run-time trap instead of wrapping silently. Asking anInt32formultipliedReportingOverflow(by:)on those values reportsoverflow: true. WithIntthe same product is 1000000000000.
Complexity
Time: O(n log n). Sorting the car numbers takes O(n log n). The loop then visits each car once and does a constant amount of work, so it is O(n).
Space: O(n). The sorted array order holds n numbers, and the stack fleets can hold up to n as well, when no car ever catches another.
Edge cases and common mistakes
- A single car.
target = 10,position = [3],speed = [3]gives 1: one car is one fleet. - Input not in road order. The positions are not sorted in the input. For
target = 10,position = [0, 4, 2],speed = [2, 1, 3], the method sorts first and returns 1. - Using >= in the helper. A car that arrives at exactly the same time as the fleet ahead joins it. With a non-strict comparison it would start a fleet of its own, and the first example would give 4 instead of 3.
- Cars that never meet. If every car is slower than the one ahead of it, none catches up. For
target = 10,position = [0, 2, 4, 6, 8]andspeed = [1, 1, 1, 1, 1], the answer is 5, because equal speeds keep a constant gap. - Faster cars behind. A fast car behind a slow one doesn't make a second fleet:
target = 10,position = [0, 2, 4, 6, 8],speed = [5, 4, 3, 2, 1]gives 1. - Comparing positions instead of times. A car far behind with a high speed can still catch a nearby slow car. The arrival times decide, not the starting miles.
- Sorting the positions alone. If you sort
positionwithout its speeds, the pairs break up. Sort the car numbers.
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 = [6, 8],speed = [3, 2]gives 2.target = 10,position = [0, 2, 4, 6, 8],speed = [1, 1, 1, 1, 1]gives 5.
