Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12.
The car starting at 0 does not catch up to any other car, so it is a fleet by itself.
The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
Note that no other cars meet these fleets before the destination, so the answer is 3.

Example 2:

Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation: There is only one car, hence there is only one fleet.

Example 3:

Input: target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
Explanation:
The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The fleet moves at speed 2.
Then, the fleet (speed 2) and the car starting at 4 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

Solution

Method 1 - Using Kinematics, stack and sorting

As illustrated in the example, Vehicle 1 is closest to the target and will lead a fleet since no vehicle behind it can overtake it. Vehicle 2, starting farther away but moving faster, would ideally reach the target first if Vehicle 1 wasn't ahead. However, Vehicle 2 will join the fleet led by Vehicle 1 upon catching up. Vehicle 3 arrives later (at t2 time) than the fleet in front and thus forms its own fleet.

car-fleet-problem-pos-time-graph.excalidraw

We can take following steps:

Sort the vehicles by their (position, speed) pairs.
The first vehicle will form its own fleet. From the second vehicle onward, compare each vehicle's ideal arrival time with the top of the stack, representing the latest arrival time of the current fleet.
If a vehicle arrives earlier, it joins the existing fleet.
Otherwise, it starts a new fleet, and its arrival time is added to the stack.
The stack then contains the distinct arrival times, representing the number of fleets.

Code

[{"language":"Java","code":"class Solution {\n    public int carFleet(int target, int[] position, int[] speed) {\n        int n = position.length;\n        Car[] cars = new Car[n];\n        \n        for (int i = 0; i < n; i++) {\n            cars[i] = new Car(position[i], (double) (target - position[i]) / speed[i]);\n        }\n        \n        Arrays.sort(cars, (a, b) -> Double.compare(b.position, a.position));\n        \n        Stack<Double> stack = new Stack<>();\n        \n        for (Car car : cars) {\n            if (stack.isEmpty() || car.time > stack.peek()) {\n                stack.push(car.time);\n            }\n        }\n        \n        return stack.size();\n    }\n    \n    class Car {\n        int position;\n        double time;\n        \n        Car(int position, double time) {\n            this.position = position;\n            this.time = time;\n        }\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n        stack = []\n        cars = sorted(zip(position, speed), reverse=True)\n        \n        for pos, vel in cars:\n            time = (target - pos) / vel\n            if not stack or time > stack[-1]:\n                stack.append(time)\n        \n        return len(stack)","lang":"python"}]

Method 2 - Using Sorting

Here is the approach:

Calculate Arrival Times: For each car, calculate its time to reach the target using the formula (target - pos[i]) / speed[i]

Related Tags