853. Car Fleet

At a Glance

Topic: stack
Pattern: Two Pointers + monotonic speed ordering
Difficulty: Medium
Companies: Google, Amazon, Microsoft, Apple, Meta
Frequency: Medium
LeetCode: 853

n cars start at unique positions on a 1D line, each with a position and speed toward a target. A fleet is cars that meet or any slower car ahead blocks faster followers. Return how many fleets arrive at the target.

Recognition Cues

Sort by descending start position (or ascending with reverse logic)
Time to target = (target - position) / speed as monotonic decision
Stack of arrival times: pop while current car catches prior fleet

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — simulation — O(n log n) sort + event queue possible but heavy.
Better — sort cars by position; stack effective arrival times — O(n log n) from sort, O(n) processing.
Optimal — same: sort + single pass from target backward (or forward with stack) — count merges.

Optimal Solution

Go

import "sort"

type car struct {
	position int
	speed    int
}

func carFleet(target int, position []int, speed []int) int {
	n := len(position)
	cars := make([]car, n)
	for index := 0; index < n; index++ {
		cars[index] = car{position: position[index], speed: speed[index]}
	}
	sort.Slice(cars, func(indexFirst, indexSecond int) bool {
		return cars[indexFirst].position > cars[indexSecond].position
	})
	times := make([]float64, 0, n)
	for index := 0; index < n; index++ {
		eta := float64(target-cars[index].position) / float64(cars[index].speed)
		for len(times) > 0 && eta >= times[len(times)-1] {
			times = times[:len(times)-1]
		}
		times = append(times, eta)
	}
	return len(times)
}

JavaScript

function carFleet(target, position, speed) {
	const cars = position.map((pos, index) => ({
		position: pos,
		speed: speed[index],
	}));
	cars.sort((a, b) => b.position - a.position);
	const arrivalTimes = [];
	for (const car of cars) {
		const timeToTarget = (target - car.position) / car.speed;
		while (
			arrivalTimes.length > 0 &&
			timeToTarget >= arrivalTimes[arrivalTimes.length - 1]
		) {
			arrivalTimes.pop();
		}
		arrivalTimes.push(timeToTarget);
	}
	return arrivalTimes.length;
}

Walkthrough

Sort cars from closest to target to farthest. Each car either forms a new fleet (push time) or catches the fleet in front (pop while eta >= top, then push).

Invariant: times stack is strictly increasing effective arrival times of surviving fleets from near to far.

Edge Cases

All cars same speed (fleets merge by position only)
Single car
Target already reached? (positions strictly less than target per problem)

Pitfalls

Sorting ascending then incorrect merge logic
Integer division of times — use float for comparison

Variants

With lanes / no-passing different rules.
Count fleet leaders at each time tick — event simulation.

Mind-Map Tags

#stack #sort-by-position #arrival-time #merge-fleets #greedy