-
Notifications
You must be signed in to change notification settings - Fork 0
056 — Car Fleet
LeetCode 853 · Medium. n cars are heading to the same destination, target, along a one-lane road. Car i starts at position[i] and drives at constant speed[i]. A car can never pass the car ahead of it — if it catches up, it slows down and travels at that car's speed from then on, forming a single "fleet" that arrives together. Return the number of distinct fleets that will arrive at the destination.
Picture a one-lane highway with no passing allowed, all cars heading to the same finish line. A slow car up ahead is a rolling roadblock — anyone faster behind it will eventually bunch up right on its bumper and be forced to crawl at its pace for the rest of the trip. So the question "how many fleets arrive?" is really "how many cars, scanning from the front of the pack to the back, are slow enough that nobody catches them, and fast enough that they aren't caught by whoever's directly ahead?" Work from the car closest to the destination backward: each car either takes longer to reach the finish than every fleet already accounted for ahead of it (so it never catches up — it's a brand-new, trailing fleet) or it doesn't (so it merges into the fleet ahead and effectively disappears as its own entity).
"Cars can't pass, and merge into a fleet moving at the slower speed" is a textbook monotonic-stack cue in disguise: after sorting by starting position, the question of "does this car form a new fleet or merge into the one ahead" only ever depends on comparing against the most recently confirmed fleet's arrival time — never anything further back. That "only ever needs the most recent still-relevant value" property is exactly what a stack (here, of arrival times) is built for.
Sort the cars by starting position (closest to the target first) and compute each car's own arrival time (ignoring merging). Then, for each car, check it against every car ahead of it, not just the nearest fleet, to decide whether it's blocked from forming its own new fleet.
func carFleetBruteForce(_ target: Int, _ position: [Int], _ speed: [Int]) -> Int {
let n = position.count
guard n > 0 else { return 0 }
let cars = zip(position, speed).sorted { $0.0 > $1.0 } // closest to target first
let times: [Double] = cars.map { Double(target - $0.0) / Double($0.1) }
var fleetCount = 0
for i in 0..<n {
var blockedByAnEarlierCar = false
for j in 0..<i {
if times[j] >= times[i] {
blockedByAnEarlierCar = true
break
}
}
if !blockedByAnEarlierCar {
fleetCount += 1
}
}
return fleetCount
}Big-O: O(n log n) for the sort, plus O(n²) for the nested comparison of every car against every car ahead of it — O(n²) overall. O(n) space for the sorted cars and times.
Sort the same way, then process cars from closest-to-target to farthest, keeping a stack of confirmed fleets' arrival times. A car merges into the fleet immediately ahead (the stack's top) if its own time doesn't exceed that fleet's time; otherwise it's slow enough to trail behind as its own new fleet, so push its time.
func carFleet(_ target: Int, _ position: [Int], _ speed: [Int]) -> Int {
let n = position.count
guard n > 0 else { return 0 }
let cars = zip(position, speed).sorted { $0.0 > $1.0 } // closest to target first
var stack: [Double] = [] // arrival times of confirmed fleets
for (pos, spd) in cars {
let time = Double(target - pos) / Double(spd)
if let fleetAheadTime = stack.last, time <= fleetAheadTime {
continue // catches up to (or ties) the fleet ahead — merges, doesn't form a new fleet
}
stack.append(time) // slower than every fleet ahead — becomes its own new trailing fleet
}
return stack.count
}
// smoke test
print(carFleet(12, [10, 8, 0, 5, 3], [2, 4, 1, 1, 3])) // 3
print(carFleet(10, [3], [3])) // 1Big-O: O(n log n) time, dominated by the sort — the scan itself is O(n) since each car is pushed at most once and compared against the stack's top a constant number of times. O(n) space for the sorted cars and the stack.
The brute force re-checks a car against every car ahead of it, but that's redundant: if a car doesn't catch the fleet immediately in front of it, it can't possibly catch anything further ahead either (it would have had to pass the fleet directly ahead first, which is disallowed). So the only comparison that ever matters is against the most recently confirmed fleet's time — exactly what stack.last gives for free. Collapsing "compare against everyone ahead" down to "compare against the top of the stack" is what turns the O(n²) scan into a single O(n) pass once the cars are sorted.
- Monotonic Stack — the genuine pattern: the stack of fleet arrival times is built bottom-to-top in strictly increasing order (each new fleet must be slower than every fleet ahead of it), the same "only the most recent surviving candidate matters" invariant as any monotonic stack.
- Stacks — the stack of confirmed fleet times, pushed and never popped once confirmed.
-
Big-O Notation — for the
O(n²)→O(n log n)reasoning above.
Car Fleet is a one-lane highway with no passing — sort cars by how close they are to the finish, and each one either trails the fleet already confirmed ahead of it, or, if it's too slow to ever catch up, becomes the leader of a brand-new fleet of its own.
For target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3], compute each car's individual arrival time (ignoring merging), sort by position descending, and trace the optimal algorithm's stack after processing each car. Which car's individual time is slower than the car directly behind it in the original array, and why does that make them merge into one fleet rather than the faster car passing it?
⬅️ Previous: Daily Temperatures · Next: Largest Rectangle in Histogram ➡️