#853 Car Fleet
the problem
In plain words
n cars drive toward target on a one-lane road. Car i starts at position[i] with speed[i]. A car can't pass the car ahead; when it catches up it slows down and they move together as one fleet. A car that catches a fleet exactly at the target also joins it. How many fleets arrive?
in target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
out 3
Cars at 10 and 8 meet at 12. The car at 0 is alone. Cars at 5 and 3 meet at 6.
in target = 10, position = [3], speed = [3]
out 1
in target = 100, position = [0,2,4], speed = [4,2,1]
out 1
Alone they would arrive at times 25, 49 and 96. The car at 4 is the slowest and leads; the two cars behind catch it.
- 1 ≤ n ≤ 10⁵
- 0 < target ≤ 10⁶
- 0 ≤ position[i] < target, all distinct
- 0 < speed[i] ≤ 10⁶
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternMonotonic stack
Look at cars from the one closest to the target backwards. A car whose solo arrival time is ≤ the fleet ahead's time catches up and merges; a slower car starts a new fleet.
solutions
From brute force to optimal
A car leads its own fleet exactly when every car ahead of it arrives sooner on its own. Check that rule for each car.
- For each car i, compute its solo time (target − position) / speed.
- Scan every car j with a bigger position: if j's time ≥ i's time, car i catches j's fleet — not a leader.
- Count the leaders.
Every car is compared with every other car.
A few counters, no sorting.
class Solution { public int carFleet(int target, int[] position, int[] speed) { int n = position.length, fleets = 0; for (int i = 0; i < n; i++) { double mine = (double) (target - position[i]) / speed[i]; boolean leader = true; // leads a fleet if every car ahead arrives sooner for (int j = 0; j < n; j++) { double theirs = (double) (target - position[j]) / speed[j]; if (position[j] > position[i] && theirs >= mine) leader = false; // it catches that car } if (leader) fleets++; } return fleets; }}Process cars from front to back. The stack holds the arrival time of each fleet's leader.
- Sort car indices by position, descending.
- time = (target − position) / speed, as a double.
- If the stack is empty or time > top: push (a new, slower fleet). Otherwise the car merges.
- Answer = stack size.
Sorting dominates; the scan is O(n).
The sorted order and the stack.
class Solution { public int carFleet(int target, int[] position, int[] speed) { int n = position.length; Integer[] order = new Integer[n]; for (int i = 0; i < n; i++) order[i] = i; Arrays.sort(order, (a, b) -> position[b] - position[a]); // closest to target first Deque<Double> stack = new ArrayDeque<>(); // arrival time of each fleet's leader for (int i : order) { double time = (double) (target - position[i]) / speed[i]; if (stack.isEmpty() || time > stack.peek()) { stack.push(time); // slower than the fleet ahead: a new fleet } // else: it catches the fleet ahead and is blocked by it — merges, nothing to push } return stack.size(); }}Only the top of the stack is ever read, so keep just the slowest arrival time ahead and a counter.
- Sort cars by position descending.
- If time > slowestAhead: fleets++, slowestAhead = time.
Still the sort.
The sorted copy (the scan itself is O(1)).
class Solution { public int carFleet(int target, int[] position, int[] speed) { int n = position.length; int[][] cars = new int[n][]; for (int i = 0; i < n; i++) cars[i] = new int[] {position[i], speed[i]}; Arrays.sort(cars, (a, b) -> Integer.compare(b[0], a[0])); int fleets = 0; double slowestAhead = 0; // only the top of the stack was ever read for (int[] car : cars) { double time = (double) (target - car[0]) / car[1]; if (time > slowestAhead) { fleets++; slowestAhead = time; } } return fleets; }}in the room
How to say it in the interview
talk track
- Draw the road. Say: "the car nearest the target is never blocked, so start there."
- Explain merging: if I would arrive no later than the car ahead, I must catch it and get stuck behind it.
- Mention why times are doubles: (target − position) / speed is usually fractional.
traps
- Integer division when computing time — 7 / 2 = 3 hides real differences. Cast to double.
- Sorting ascending and scanning from the back of the road — the merging logic then points the wrong way.
what they ask next
Follow-ups
Car Fleet II (LC 1776): when does each car collide?
Scan from the front car backwards with a monotonic stack of cars ahead. Pop cars you can never hit (as fast or faster) and cars that merge into a fleet before you would reach them; the top then gives your collision time.
before you submit
Edge cases to test
- One car → one fleet.
- A car that catches up exactly at the target still joins: equal times merge, so compare with >.
- Positions come unsorted — sort by position before scanning.
practise next
Similar problems
- #739Daily TemperaturesMediumin Stacks
- #735Asteroid CollisionMediumin Stacks