Car Fleet

Problem

Cars at positions on a 1-D road head to a target. Each has a constant speed but cars cannot pass — slower cars in front turn the line into a fleet that arrives together. Given the target distance, positions array and speeds array, return the number of fleets that reach the target.

Constraints

• 1 ≤ n ≤ 10⁵
• 0 < target ≤ 10⁶
• 0 ≤ position[i] < target
• 0 < speed[i] ≤ 10⁶

Approach — Stack

This is a Stack problem. The idea: scan the input once, pushing work onto a stack and popping when the top can be resolved, so the stack always reflects what's still open. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def carFleet(self, target, position, speed):
        cars = sorted(zip(position, speed), reverse=True)
        fleets = 0
        cur = -1.0
        for pos, sp in cars:
            t = (target - pos) / sp
            if t > cur:
                fleets += 1; cur = t
        return fleets

Java

import java.util.*;

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        double[][] cars = new double[n][2];
        for (int i = 0; i < n; i++) {
            cars[i][0] = position[i];
            cars[i][1] = (double)(target - position[i]) / speed[i];
        }
        // Closest to target first.
        Arrays.sort(cars, (a, b) -> Double.compare(b[0], a[0]));
        // Monotonic stack of fleet arrival times. A car whose time is
        // <= the fleet ahead of it (stack top) catches up and merges,
        // so only a strictly slower time starts a new fleet.
        Deque<Double> fleets = new ArrayDeque<>();
        for (double[] c : cars) {
            if (fleets.isEmpty() || c[1] > fleets.peek()) fleets.push(c[1]);
        }
        return fleets.size();
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.