Problem overview
The method carFleet receives a target distance and two arrays, position and speed, one entry per car. Car i starts at mile position(i) and drives at speed(i) miles per hour toward the target on a one-lane road. A car can't pass the one ahead. 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 of one. A car that catches up exactly at the target joins the fleet. 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 both need 1 hour, so the second one catches the first exactly at the target: one fleet. The car from mile 5 (1 mile per hour) would need 7 hours, and the car from mile 3 (3 miles per hour) catches it and follows it: a second fleet. The car from mile 0 never catches anyone: a third. The answer is 3.
The lesson asks for O(n log n) time and O(n) extra space.
Approach: go from the front of the road, compare arrival times
Simulating the road minute by minute is awkward, because the cars change speed when they meet. A simpler observation avoids it: a car's arrival time if nothing blocked it is (target - position) / speed. A car that is behind another car and would arrive no later than it must catch it at the latest at the target, and then it is part of that fleet. A car that would arrive later never catches the car ahead, so it starts a new fleet.
So the order along the road is the only thing that matters. Sort the cars from the one closest to the target to the one farthest, and process them in that order. Keep a stack of the fleets found so far. The fleet on top is always the one just ahead of the next car, and also the one that arrives last. Compare the new car with the top fleet only:
- If the stack is empty, or the car would arrive strictly later than the top fleet, it starts a new fleet. Push it.
- Otherwise it catches the top fleet and joins it. Do nothing.
A fleet is stored as the number of its lead car, because the lead car was never slowed down: the fleet arrives when that car would arrive on its own. The answer is the size of the stack.
Here is that process on the first example:
order [0,1,3,4,2]
car=0 position=10 speed=2 newFleet=true fleets=1
car=1 position=8 speed=4 newFleet=false fleets=1
car=3 position=5 speed=1 newFleet=true fleets=2
car=4 position=3 speed=3 newFleet=false fleets=2
car=2 position=0 speed=1 newFleet=true fleets=3
The comparison itself involves fractions. Instead of dividing, compare exactly by cross-multiplying. Since both speeds are positive, (target - p1) / s1 > (target - p2) / s2 is the same as (target - p1) * s2 > (target - p2) * s1. Equal times stay exactly equal this way, which matters because a tie means the car joins the fleet.
Step by step
- Sort the car numbers by position, closest to the target first.
position.indices.sortBy(car => -position(car))sorts the numbers 0 to n-1, not the positions, so each car keeps its own speed. The minus sign puts the largest positions first. - Create the stack.
mutable.Stack[Int]()in avalnamedfleetsholds the lead car of each fleet found so far. - Visit the cars in that order with
for (car <- order). - Decide whether the car starts a new fleet. The condition is
fleets.isEmpty || arrivesLater(...). The first car always starts a fleet, and later cars start one when they would arrive strictly later thanfleets.top. The||stops at the first true part, sotopis only read when the stack has something in it. - Push the car with
fleets.push(car)when it starts a fleet. Cars behind it may still catch up with this new fleet. - Return
fleets.sizeafter the loop. Every car started a fleet or joined one, so the stack holds each fleet once. - Write the helper
arrivesLater, a method that takes the target, both arrays, acarand alead, and returns aBoolean. It answers whethercar, driving alone, would arrive strictly later thanlead. Strictly, because arriving together counts as one fleet. - Compare the times without dividing. The method's value is whether
(target - position(car)).toLong * speed(lead)is greater than(target - position(lead)).toLong * speed(car).
The solution in Scala
class Solution {
def carFleet(target: Int, position: Array[Int], speed: Array[Int]): Int = {
val order = position.indices.sortBy(car => -position(car))
val fleets = mutable.Stack[Int]()
for (car <- order) {
if (fleets.isEmpty || arrivesLater(target, position, speed, car, fleets.top)) {
fleets.push(car)
}
}
fleets.size
}
def arrivesLater(target: Int, position: Array[Int], speed: Array[Int], car: Int, lead: Int): Boolean = {
(target - position(car)).toLong * speed(lead) > (target - position(lead)).toLong * speed(car)
}
}
The Scala details worth a closer look:
- The import. The lesson's editor already makes
mutableavailable. In a file of your own, addimport scala.collection.mutable. indicesandsortBy.position.indicesis the range0 until position.length.sortBysorts by the key the function returns and gives back a new sorted sequence; the original arrays are not touched. Sorting indexes is what keeps each position paired with its speed.- Why
.toLongmatters. Both factors can reach 1,000,000, so a product can reach 1,000,000,000,000, far beyond anInt's limit of about 2.1 billion. Withtarget = 1000000, one factor 1000000 and another 999999, theIntproduct wraps silently to-728379968, while theLongproduct is999999000000. Converting just the first factor is enough: aLongtimes anIntis computed as aLong. - Stack methods.
pushadds to the top,topreads the top without removing it, andsizecounts the entries. The solution never pops: a fleet stays on the stack until the end. - Two methods in one class.
arrivesLateris an ordinary method ofSolution, called fromcarFleetwithout any prefix. The order of the two definitions in the class doesn't matter. - The last expression is the value.
fleets.sizeand the comparison in the helper both return without thereturnkeyword.
Complexity
Time: O(n log n). Sorting the car numbers takes O(n log n). The loop that follows does constant work per car, so the sort is the larger part.
Space: O(n). The sorted order holds n numbers and the stack holds at most n.
Edge cases and common mistakes
- One car.
target = 10,position = [3],speed = [3]gives 1. - A chain that merges.
target = 100,position = [0, 2, 4],speed = [4, 2, 1]gives 1: each car catches the fleet ahead, and all three arrive together after 96 hours. - Arriving at the same time. The cars at miles 10 and 8 in the first example both need 1 hour. A
>=in the helper would count the tie as two fleets, which is wrong. A strict>counts the tie as one fleet. - Input in any order. The arrays are not sorted:
target = 10,position = [0, 4, 2],speed = [2, 1, 3]gives 1. Sorting the car numbers by position handles that. - Comparing with the wrong fleet. Only the top of the stack matters, since it is the fleet just ahead of the car and the last to arrive.
- Integer overflow. Multiplying in
Intcan wrap to a wrong sign and flip the comparison. Withtarget = 1000000,position = [0, 1]andspeed = [1000000, 999999], the code returns 1 because the Long comparison sees two equal times. - Dividing instead of cross-multiplying. Times such as 1/3 and 2/6 are equal as fractions, but a division result is rounded, and a tie must stay a tie. Cross-multiplying with
Longcompares the exact values.
Testing
target = 12,position = [10, 8, 0, 5, 3],speed = [2, 4, 1, 1, 3]gives3.target = 10,position = [3],speed = [3]gives1.target = 100,position = [0, 2, 4],speed = [4, 2, 1]gives1.target = 10,position = [0, 4, 2],speed = [2, 1, 3]gives1.target = 10,position = [6, 8],speed = [3, 2]gives2.target = 12,position = [10, 8],speed = [2, 4]gives1(a tie).target = 1000000,position = [0, 1],speed = [1000000, 999999]gives1.
