Car Fleet

NeetCode: Car Fleet · LeetCode: 853. Car Fleet · Difficulty: Medium

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 one ahead; it slows to match and they form a fleet. Return the number of fleets that arrive.

Example

Text

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

Brute force: compare every pair

A car is blocked, and so joins a fleet ahead of it, if some car in front would arrive at the same time or later (it catches up and has to slow down). The arrival time of car i is (target - position[i]) / speed[i], computed in double (the cast to double comes first, because int / int would truncate). Equal fractions give equal double results, so the >= comparison treats cars that arrive together as blocked. Every car that is not blocked leads its own fleet, so count the cars whose arrival time is strictly larger than the arrival time of every car ahead of them.

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 blocked = false;
            for (int j = 0; j < n; j++) {
                if (position[j] > position[i] && time[j] >= time[i]) {
                    blocked = true;
                    break;
                }
            }
            if (!blocked) {
                fleets++;
            }
        }
        return fleets;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.carFleet(10, new int[]{1, 4}, new int[]{3, 2}));
        System.out.println(s.carFleet(10, new int[]{4, 1, 0, 7}, new int[]{2, 1, 1, 1}));
    }
}

Output

1
3

Time: O(n²). Space: O(1).

Optimal: sort by position, then a stack of fleet times

Sort cars from closest to the target to farthest. Each car becomes a {position, speed} pair, and the comparator uses Integer.compare (not subtraction, which can overflow). Walk that order with a stack of fleet arrival times. If the current car would arrive later than the fleet ahead, it can't catch it and starts a new fleet. If it would arrive sooner or at the same time, it merges into that fleet, which keeps the slower fleet's time, so nothing is pushed.

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][];
        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])); // closest to target first

        Deque<Double> fleetTimes = new ArrayDeque<>();
        for (int[] car : cars) {
            double time = (double) (target - car[0]) / car[1];
            if (fleetTimes.isEmpty() || time > fleetTimes.peek()) {
                fleetTimes.push(time);
            }
        }
        return fleetTimes.size();
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.carFleet(10, new int[]{1, 4}, new int[]{3, 2}));
        System.out.println(s.carFleet(10, new int[]{4, 1, 0, 7}, new int[]{2, 1, 1, 1}));
    }
}

Output

1
3

Time: O(n log n). Space: O(n).