Skip to content
AI360Xpert
Back to Stack
Medium

Car Fleet

There are `n` cars going to the same destination along a one-lane road. The destination is `target` miles away. You are given two integer arrays `position` and `speed`, both of length `n`. A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car's speed. This group of cars is called a car fleet. Return the number of car fleets that will arrive at the destination.

Examples

Input:target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output:3
The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, arriving at 1. The car starting at 5 (speed 1) arrives alone. The cars at 0 and 3 become a fleet, arriving at 12.
Input:target = 10, position = [3], speed = [3]
Output:1
There is only one car, hence there is only one fleet.

Constraints

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

Sort and Stack

Approach

First, pair each car's position and speed, and sort them in descending order based on their starting positions (closest to target first). Calculate the time each car needs to reach the target: `(target - position) / speed`. We use a stack to keep track of the fleets. If a car takes less or equal time than the car ahead of it (top of the stack), it will catch up and form a fleet, so we don't push it. Otherwise, it forms a new fleet, and we push its time onto the stack. The size of the stack is the number of fleets.

Complexity Analysis

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

Sorting the cars by position takes O(n log n). The stack operations take O(n).

Solution.java
class Solution {    public int carFleet(int target, int[] position, int[] speed) {        if (position.length == 0) return 0;                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] = speed[i];        }                // Sort cars by position descending        Arrays.sort(cars, (a, b) -> Double.compare(b[0], a[0]));                Stack<Double> stack = new Stack<>();                for (int i = 0; i < n; i++) {            double time = (target - cars[i][0]) / cars[i][1];                        // If stack is empty or this car takes longer than the fleet ahead            if (stack.isEmpty() || time > stack.peek()) {                stack.push(time);            }            // If time <= stack.peek(), it catches up to the fleet ahead and merges        }                return stack.size();    }}