26.Car Fleet

MediumStack · 6/7

Problem

There are n cars on a one-lane road heading to the same destination at mile target. Car i starts at position[i] and drives at constant speed[i] miles per hour.

A car can never pass the car in front of it. If it catches up, it slows down and the two drive together bumper-to-bumper as a car fleet (moving at the slower car's speed). A single car is also a fleet. A car that catches a fleet exactly at target still counts as part of that fleet.

Return the number of car fleets that arrive at the destination.

Examples

Input:  target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
Output: 3
Explanation:
  Car at 10 arrives at t=1; car at 8 also reaches 12 at t=1 → one fleet.
  Car at 5 arrives at t=7; car at 3 would arrive at t=3, catches it → one fleet.
  Car at 0 arrives at t=12 and never catches anyone → its own fleet.

Input:  target = 10, position = [3], speed = [3]
Output: 1

Input:  target = 100, position = [0, 2, 4], speed = [4, 2, 1]
Output: 1
Explanation: The car at 4 needs 96 h; the cars behind would be faster, so all merge into one fleet.

Constraints

n == position.length == speed.length
1 <= n <= 10^5
0 < target <= 10^6
0 <= position[i] < target
All values of position are unique.
0 < speed[i] <= 10^6

💡 Key Insight

Only arrival times matter: car i would arrive alone at (target - position[i]) / speed[i]. Process cars from the one closest to the target backwards. A car whose solo time is <= the time of the fleet in front of it catches that fleet (and is slowed to it); a car that would take longer can never catch up and starts a new fleet. So after sorting by position, count how many times the arrival time strictly increases.

Brute Force

TimeO(n²)SpaceO(n)

Intuition

A car leads its own fleet iff it is slower to arrive than every car ahead of it — otherwise it would catch the fleet directly ahead (whose arrival time is the maximum among the cars ahead). Check that condition for each car by scanning all cars ahead.

Algorithm

Compute time[i] = (target - position[i]) / speed[i] as a double.
For each car i, check every car j with position[j] > position[i].
If time[i] > time[j] for all such j, car i is a fleet leader → fleets++.
Return fleets.

Visualization

target = 12
car (pos, time): (10, 1) (8, 1) (0, 12) (5, 7) (3, 3)

pos 10: nobody ahead                   → leader
pos 8 : time 1 vs 1 (pos 10) not >     → joins
pos 5 : 7 > 1, 7 > 1                   → leader
pos 3 : 3 > 1, 3 > 1, but 3 < 7        → joins
pos 0 : 12 > all                       → leader      fleets = 3

Code

java

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        double[] time = new double[n];
        for (int i = 0; i < n; i++) {
            time[i] = (double) (target - position[i]) / speed[i];
        }
        int fleets = 0;
        for (int i = 0; i < n; i++) {
            boolean leader = true;
            for (int j = 0; j < n; j++) {
                // a car ahead that arrives no earlier would block car i
                if (position[j] > position[i] && time[j] >= time[i]) {
                    leader = false;
                    break;
                }
            }
            if (leader) {
                fleets++;
            }
        }
        return fleets;
    }
}

Complexity

Time: O(n²) — every car is compared with every other car.
Space: O(n) — the arrival times.

Sort + Stack

TimeO(n log n)SpaceO(n)

Intuition

Sort cars by position, closest to the target first. Push each car's arrival time onto a stack. If the new time is <= the time on top, the car merges into the fleet ahead — pop it again (the fleet keeps the slower, larger time on top). The stack size at the end is the number of fleets.

Algorithm

Pair up (position, time) and sort by position descending.
For each car in that order: push its time; if the stack has ≥ 2 entries and top <= second, pop the top.
Return the stack size.

Dry Run

flowchart TD
    A["sorted by position desc<br/>(10, 1) (8, 1) (5, 7) (3, 3) (0, 12)"] --> B["push 1 → [1]"]
    B --> C["push 1, 1 <= 1 → merge<br/>stack [1]"]
    C --> D["push 7, 7 > 1 → new fleet<br/>stack [1, 7]"]
    D --> E["push 3, 3 <= 7 → merge<br/>stack [1, 7]"]
    E --> F["push 12, 12 > 7 → new fleet<br/>stack [1, 7, 12]"]
    F --> G["answer = stack size = 3"]

Code

java

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        int[][] cars = new int[n][2];
        for (int i = 0; i < n; i++) {
            cars[i][0] = position[i];
            cars[i][1] = speed[i];
        }
        // closest to the target first
        Arrays.sort(cars, (a, b) -> Integer.compare(b[0], a[0]));

        Deque<Double> stack = new ArrayDeque<>(); // arrival times of fleets
        for (int[] car : cars) {
            double time = (double) (target - car[0]) / car[1];
            stack.push(time);
            if (stack.size() >= 2) {
                double top = stack.pop();
                if (top > stack.peek()) {
                    stack.push(top); // slower than the fleet ahead: new fleet
                }
                // otherwise it caught up and merged, so it stays popped
            }
        }
        return stack.size();
    }
}

Complexity

Time: O(n log n) — dominated by sorting.
Space: O(n) — the paired array and the stack.

Sort + Track Slowest Fleet TimeOptimal

TimeO(n log n)SpaceO(n)

Intuition

The stack only ever compares against its top, so replace it with one variable fleetTime — the arrival time of the fleet directly ahead. A car with time > fleetTime starts a new fleet and becomes the new fleetTime; otherwise it merges and nothing changes. Sorting an array of car indices (by position) avoids copying positions and speeds into pairs.

Algorithm

Create an index array sorted by position descending.
fleets = 0, fleetTime = 0.
For each index i in that order:
- time = (target - position[i]) / speed[i].
- If time > fleetTime: fleets++, fleetTime = time.
Return fleets.

Dry Run

order (pos desc):   10    8    5    3    0
time:                1    1    7    3   12
fleetTime before:    0    1    1    7    7
new fleet?          yes   no  yes   no  yes
fleetTime after:     1    1    7    7   12      fleets = 3

Code

java

import java.util.Arrays;

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;
        }
        // process cars from closest-to-target to farthest
        Arrays.sort(order, (a, b) -> Integer.compare(position[b], position[a]));

        int fleets = 0;
        double fleetTime = 0; // arrival time of the fleet directly ahead
        for (int i : order) {
            double time = (double) (target - position[i]) / speed[i];
            if (time > fleetTime) {
                fleets++;          // cannot catch the fleet ahead
                fleetTime = time;  // it becomes the new blocking fleet
            }
        }
        return fleets;
    }
}

Complexity

Time: O(n log n) — sorting; the scan is O(n).
Space: O(n) — the index array.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(n)
Sort + Stack	O(n log n)	O(n)
Sort + Fleet Time	O(n log n)	O(n)

Common Pitfalls

Computing times with integer division — (12 - 3) / 3 and (12 - 4) / 3 both give 3; cast to double.
Processing cars from the back of the road: a car's fate depends on the fleet ahead, so sort by position descending.
Using >= when deciding a new fleet: equal arrival times mean the cars meet exactly at the target, which counts as one fleet.
Sorting position alone and losing track of which speed belongs to which car — sort pairs or sort indices.