TRT
Sign in
mediumFoundationsLeetCode#sort then stack#arrival times

Car fleet

Count how many groups of cars arrive at a destination, by sorting by position and stacking arrival times.

The Runtime Theory Team1 min read
Taught inDeques and monotonic stacksA deque works at both ends in O(1). A monotonic stack keeps its items in sorted order by popping everything a new item beats, which answers 'what is the next bigger value?' for every element in one pass.
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

intarget = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]

out3

intarget = 10, position = [3], speed = [3]

out1

intarget = 100, position = [0, 2, 4], speed = [4, 2, 1]

out1

Cars drive toward target on a one-lane road. A car can't pass the one ahead; if it catches up, they drive together as a fleet at the slower speed. Given each car's position and speed, return how many fleets arrive.

Before you code

What decides fleets is each car's arrival time if it drove alone: (target - position) / speed. A car catches the car ahead of it exactly when it would otherwise arrive earlier.

Hints

  1. Sort the cars by position, closest to the target first.
  2. Walk them in that order with a stack of fleet arrival times. If a car's time is greater than the top, it can't catch up: it starts a new fleet, so push its time.
  3. Otherwise it joins the fleet ahead and is not pushed.
  4. The answer is the size of the stack. The times on it increase, which makes it a monotonic stack.

Production & complexity notes

When solving Car fleet on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Deques and monotonic stacks to reinforce the underlying pattern.

What it practices

Keeping only the items that still matter on a stack, from Deques and monotonic stacks.

More practice in this track

hard · dsaDesign a skip listmedium · dsaDesign a bounded blocking queueeasy · dsaRange sum query: immutable

Not started

Sign in to save your learning progress.

Sign in to save