Problem 9.7 · Stack and Monotonic StackMedium

Car Fleet

What it teaches: Sort by position, then compare arrival times from the front: a car that would arrive sooner than the fleet ahead joins it.

Practise it on judges as “Car Fleet”.

The problem

n cars drive towards target on a one-lane road. Car i starts at position[i] with speed[i]. A car can't pass the car ahead; it slows down and they drive together as one fleet. How many fleets arrive at the target?

Example 1

Input: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
Output: 3

Example 2

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

Constraints

1 ≤ n ≤ 10⁵
Positions are distinct and < target

Pattern clues in the wording

→ Objects can't overtake: order by position matters
→ Each car is compared with the fleet just ahead of it

These clues point to Monotonic Stack: Keep a stack whose values only increase (or decrease); each element pops everything it beats, finding "next greater/smaller" in one pass.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	target = 12 position = [10,8,0,5,3] speed = [2,4,1,1,3]	3
2	target = 10 position = [3] speed = [3]	1
3	target = 100 position = [0,2,4] speed = [4,2,1]	1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: sort and track fleet arrival times · O(n log n)

Optimal: sort and track fleet arrival times

Time O(n log n) Space O(n)

Sort by position descending. Walk from the car nearest the target. Its time alone is (target − pos) / speed. If it's greater than the current leading fleet's time, it can't catch up: it starts a new fleet. Otherwise it merges and adopts that fleet's time. (This is a stack of fleet times where only the top matters.)

Approach 1

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;
        Arrays.sort(order, (a, b) -> Integer.compare(position[b], position[a]));   // closest first
        int fleets = 0;
        double leadTime = 0;
        for (int i : order) {
            double time = (double) (target - position[i]) / speed[i];
            if (time > leadTime) {          // can't catch the fleet ahead: new fleet
                fleets++;
                leadTime = time;
            }
        }
        return fleets;
    }
}

Verdict: Sorting dominates; the scan is linear.

Before you submit

Edge cases and common mistakes

Test these inputs

One car
All cars merge into one fleet
No cars catch up

Mistakes people make

Sorting by speed instead of position.
Using integer division for times.
Using >= so cars arriving at exactly the same time count as separate fleets.

Interview

Follow-up questions

Why does a car arriving at the same time join the fleet?

Command Palette

The problem

Approaches

Optimal: sort and track fleet arrival times

Edge cases and common mistakes

Follow-up questions