loading

Car Fleet — Step-by-Step Visualization

mediumLeetCode #853ArrayStackSortingMonotonic Stack

There are `n` cars going to the same destination at `target` miles. Each car `i` has a position `position[i]` and speed `speed[i]`. A car fleet is a group of cars that travel together at the same speed. Return the number of car fleets that will arrive at the destination.

Algorithm Pattern

Monotonic Stack (Sorting by Position)

Key Idea

Sort cars by position descending. A car forms a new fleet only if it takes strictly longer to arrive than the car in front of it on the stack.

Step-by-Step Approach

  1. Sort cars by position descending (closest to target first).
  2. For each car compute time = (target - pos) / speed.
  3. If stack is empty or car's time > stack top, it forms a new fleet → push.
  4. Otherwise, it catches up to the fleet ahead → discard.
  5. Return stack length.

Common Gotchas

  • Cars that catch up to a fleet ahead travel at the slower car's speed — they merge.
  • Sorting descending by position is crucial so we process front cars first.

Related Problems

← All problems