LeetCode 853 · Medium · Stack

Car Fleet

Cars drive one way down a single-lane road toward target. A faster car that catches a slower one cannot pass, so they drive on together as one fleet. Count the fleets that reach the target.

O(n log n)time · the sort
O(n)space
arrival timesstack of fleet leaders

target: 1–100 · 1–10 cars · positions distinct, 0 to target − 1 · speeds 1 to 10, one per car

car0arrives at

stackfleet arrival times

public int carFleet(int target, int[] position, int[] speed) { int n = position.length; int[][] pair = new int[n][2]; for (int i = 0; i < n; i++) { pair[i][0] = position[i]; pair[i][1] = speed[i]; } Arrays.sort(pair, (a, b) -> b[0] - a[0]); // closest first List<Double> stack = new ArrayList<>(); // fleet arrival times for (int[] car : pair) { stack.add((double) (target - car[0]) / car[1]); int k = stack.size(); if (k >= 2 && stack.get(k - 1) <= stack.get(k - 2)) { stack.remove(k - 1); // joins the fleet ahead } } return stack.size();}
p, s
—
time
—
stack
[]
fleets
0

Why it works

  1. Brute force simulates the road step by step, merging cars that meet. The number of steps depends on the distances and speeds, and each step touches every car.
  2. Key insight: only arrival times matter. Ignoring everyone else, a car would reach the target at (target - p) / s. Go from the car closest to the target backwards. If a car would arrive no later than the fleet just ahead of it, it must catch that fleet on the way and then drive at its speed: it joins it. Otherwise it is slower, never catches up, and leads a new fleet.
  3. O(n log n) time for the sort; the pass itself is O(n) with one push and at most one pop per car. Invariant: the stack's arrival times strictly increase from bottom to top, one per fleet.
  4. Pitfall: compare with the fleet, not with the car ahead. A merged car's own time is gone; the fleet moves at its leader's pace, which is what the stack top keeps. And <=, not <: two cars arriving at the same moment meet exactly at the target, and that counts as one fleet.
  5. Without the stack: keep only the latest fleet's time and count how often a car's time exceeds it: O(1) extra space after the sort. Related: Car Fleet II (1776) asks when each car collides.