Problem overview
The function carFleet receives target, the distance in miles from the start of a one-lane road to the destination, and two slices of the same length, position and speed. 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, it slows down and drives on with it 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 catches up with a fleet exactly at target is part of that fleet. The function returns the number of fleets that arrive at target.
For target = 12, position = [10, 8, 0, 5, 3] and speed = [2, 4, 1, 1, 3] the answer is 3:
- The car from mile 10 would arrive after 1 hour, and so would the car from mile 8. The second one catches up exactly at the target, so they are one fleet.
- The car from mile 5 (speed 1) would need 7 hours, the car from mile 3 (speed 3) only 3. They meet at mile 6 after 1 hour and drive on at speed 1: a second fleet.
- The car from mile 0 would need 12 hours and never catches anyone: a third fleet.
A single car is one fleet. With target = 100, position = [0, 2, 4] and speed = [4, 2, 1] the result is 1: the cars merge one by one and all three arrive together.
The lesson asks for O(n log n) time and O(n) extra space.
Approach: go from the front car backwards
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. The car at the front can never be blocked, so it leads a fleet. If nothing slowed it down, car i would arrive after (target - position[i]) / speed[i] hours; call this its time alone.
For each car going backwards, compare its time alone with the fleet just ahead of it:
- If it would arrive no later, it catches up with that fleet at the latest at the target, and joins it. Nothing changes.
- If it would arrive later, it never catches up. It leads a new fleet, which the cars behind it may still join.
A fleet arrives when the car that leads it would arrive alone, because that car was never slowed down. So a stack of lead cars is all we need, and the fleet just ahead of the next car is always the one on top. It is also the one that arrives last so far, because each new fleet arrives strictly later than the one before. The answer is the size of the stack.
Sorting the cars by position costs O(n log n) and the pass after it is O(n), so sorting dominates. In the first example the cars sort like this, closest to the target first, and their times alone are:
[0 1 3 4 2]
car 0 pos 10 speed 2 alone: 1
car 1 pos 8 speed 4 alone: 1
car 3 pos 5 speed 1 alone: 7
car 4 pos 3 speed 3 alone: 3
car 2 pos 0 speed 1 alone: 12
The first line is the car numbers in order. Car 0 starts a fleet (time 1). Car 1 also takes 1 hour, which is not later, so it joins. Car 3 takes 7, later than 1: a new fleet. Car 4 takes 3, not later than 7: it joins that fleet. Car 2 takes 12, later than 7: a third fleet.
Step by step
- Store the number of cars in
nwithlen(position). - Create
orderwithmake([]int, n). It holds car numbers, not positions. Sorting the numbers keeps each position together with its speed: the carorder[k]starts atposition[order[k]]and drives atspeed[order[k]]. - Fill it with 0 to n-1 in a
for i := range orderloop, settingorder[i] = i. - Sort by position, closest to the target first with
sort.Slice. The function it takes receives two indexes intoorder, and returnstruewhen the element at the first index goes first. So it looks up the car numbers and comparesposition[order[a]] > position[order[b]]. - Create
fleets, an empty[]intused as the stack. For each fleet, it keeps the number of the car that leads it. - Visit the cars in sorted order with
for _, car := range order. - Decide if the car starts a new fleet. It does when the stack is empty, or when it would arrive later than the fleet on top,
fleets[len(fleets)-1]. The comparison is the helperarrivesLater, written in the last steps. - Push the car with
append, assigned back tofleets. Otherwise it joined the top fleet and nothing is done. - Return
len(fleets): every car either started a fleet or joined the one ahead, so each fleet is on the stack once. - Write the helper
arrivesLater, takingtarget,position,speed,carandlead, and returning abool. It answers whethercar, driving alone, would arrive strictly later thanlead. - Compare the times without dividing. Alone,
carneeds (target - position[car]) /speed[car]hours andleadneeds (target - position[lead]) /speed[lead]. Multiplying both sides by the two speeds, which are positive, keeps the comparison and removes the fractions. The helper returns whether(target-position[car])*speed[lead]is greater than(target-position[lead])*speed[car].
The solution in Go
func carFleet(target int, position []int, speed []int) int {
n := len(position)
order := make([]int, n)
for i := range order {
order[i] = i
}
sort.Slice(order, func(a, b int) bool { return position[order[a]] > position[order[b]] })
fleets := []int{}
for _, car := range order {
if len(fleets) == 0 || arrivesLater(target, position, speed, car, fleets[len(fleets)-1]) {
fleets = append(fleets, car)
}
}
return len(fleets)
}
func arrivesLater(target int, position []int, speed []int, car int, lead int) bool {
return (target-position[car])*speed[lead] > (target-position[lead])*speed[car]
}
Go details worth knowing
sort.Slicegives indexes, not values. Its comparison function gets two positions in the slice being sorted, not two elements. That is why the code writesposition[order[a]]: firstorder[a]to get the car, thenpositionof that car. Sortingorderleavespositionandspeeduntouched: after the sort, they still print as[10 8 0 5 3] [2 4 1 1 3].- The sort is not stable. That is no problem here, because all positions are different, so no two cars tie.
for i := range orderover a slice, keeping only the index, is the usual way to fill a slice with 0 to n-1.- Short-circuit
||. When the stack is empty,len(fleets) == 0is true and the right side never runs, sofleets[len(fleets)-1]is never read from an empty slice. - Exact comparison with 64-bit integers. The distances and the speeds go up to 1,000,000, so a product can reach 10^12 (a million times a million). That doesn't fit in 32 bits, but Go's
intis 64 bits here, so it fits. The cross-multiplied form compares integers exactly, so equal arrival times stay equal:carFleet(10, []int{8, 6}, []int{1, 2})has two cars that both would arrive after 2 hours when driving alone, and the answer is 1. - Helper after its caller. Go doesn't need a function to be defined before the code that calls it.
Complexity
Time: O(n log n). Sorting takes O(n log n). The pass over the sorted cars does constant work per car, which is O(n) in total, so sorting is the larger part.
Space: O(n). order and fleets hold at most n car numbers each.
Edge cases and common mistakes
- One car. The stack is empty at the first car, which starts a fleet.
carFleet(10, []int{3}, []int{3})returns 1. - Arriving at the same moment. The comparison must be strictly greater. A car that reaches the target at the same time as the fleet ahead catches up exactly there, and the lesson counts it as part of that fleet. Using
>=would count it as a new one. - Comparing against the wrong fleet. A car can only meet the fleet just ahead, and that is the top of the stack. Fleets deeper in the stack arrive earlier, so they can't matter.
- Visiting the cars in the input order. The cars are not given sorted. Without the sort, the stack would compare cars that have other cars between them.
- Sorting the positions alone. If
positionis sorted butspeedis not moved with it, each speed ends up with the wrong car. Sorting the car numbers avoids that. - Fast cars behind slow ones. A car that is much faster than the one ahead can't pass it. In the example
[0, 2, 4]with speeds[4, 2, 1], the car at mile 0 is the fastest, but it ends in the same fleet, at speed 1, and arrives after 96 hours.
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 = [8, 6],speed = [1, 2]gives 1: both cars reach the target at the same moment.target = 10,position = [6, 8],speed = [3, 2]gives 2: the car at mile 8 needs 1 hour and the car at mile 6 needs 4/3 of an hour, so the rear car never catches up.
