Car Fleet

Medium

The problem

Cars start at different positions on a one-lane road and all drive toward the same target at their own constant speeds. A car cannot pass the car in front of it; if it catches up, it slows down and drives right behind it, and they arrive together as one fleet. Return how many fleets arrive at the target. A single car is also a fleet.

Example 1
Input: target = 10, position = [6, 2, 4], speed = [3, 1, 2]
Output: 3
The car at 6 needs 4/3 hours, the car at 4 needs 6/2 = 3 hours and the car at 2 needs 8/1 = 8 hours. Each is slower than the cars ahead of it, so none of them catches up.
Example 2
Input: target = 20, position = [0, 4, 8], speed = [5, 3, 1]
Output: 1
The car at 8 needs 12 hours. The cars behind it would arrive sooner but cannot pass, so all three arrive together as 1 fleet.
Example 3
Input: target = 100, position = [0], speed = [1]
Output: 1
One car is one fleet.

Limits

1 ≤ position.length = speed.length ≤ 100,000
0 ≤ position[i] < target, and all positions are different
speed[i] > 0

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

A car can never pass the one ahead. Compute how long each car needs to reach the target.

The idea

Sort cars by start position from nearest the target backwards; compute arrival time = (target−pos)/speed. A car whose time is greater than the fleet ahead starts a new fleet; otherwise it merges into it.

Target: O(n log n) time, O(n) space

Go function shape

func carFleet(target int, position []int, speed []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// CarFleet: sort by position, nearest the target first, and compute each car's arrival time.
// A car behind can never pass, so if it would arrive sooner than the fleet ahead it catches up and joins it.
// Only a car that arrives LATER than every fleet ahead leads a new fleet.
func CarFleet(target int, position, speed []int) int {
	idx := make([]int, len(position))
	for i := range idx {
		idx[i] = i
	}
	sort.Slice(idx, func(a, b int) bool { return position[idx[a]] > position[idx[b]] })
	fleets := 0
	slowest := 0.0
	for _, i := range idx {
		t := float64(target-position[i]) / float64(speed[i])
		if t > slowest { // arrives after everything ahead: cannot catch up, starts a new fleet
			fleets++
			slowest = t
		}
	}
	return fleets
}

Read the lesson: Stack Basics