Car Fleet medium

Problem Statement

There are n cars going to the same destination along a one lane road. The destination is target miles away.

Each car starts at a position position[i] miles from the destination and has a speed speed[i] miles per hour.

A car can only pass another car if it's strictly faster. It's not allowed for a slower car to overtake a faster car.

Find the number of cars that will reach the destination at or before the time when the first car arrives.

Note:

• 1 <= n <= 1000
• 1 <= target <= 10^7
• 1 <= position[i] <= target
• 1 <= speed[i] <= 10^6

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 and 8 reach the destination at time 1 and 2 respectively. The car at 0 reaches the destination at time 12. The cars at 5 and 3 reach the destination at time 3.5 and 1 respectively. The first car arrives at time 1. Since there are 3 cars arriving at time 3 or less, the answer is 3.

Example 2

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

Steps

1. Calculate arrival times: For each car, calculate the time it takes to reach the destination: time = position[i] / speed[i]. We use floating point division here to account for the possibility of non-integer times.

2. Sort by arrival time: Sort the cars in ascending order of their arrival times. This is crucial because we only care about cars that arrive before or at the same time as the first car.

3. Iterate and merge: Iterate through the sorted cars from the end (the latest arrival times). We maintain a stack to track the arrival times. If the current car's arrival time is strictly greater than the top of the stack (meaning it's slower than the car at the top of the stack), it will be overtaken by the car at the top of the stack. Thus, we don't need to consider it. Otherwise, we push its arrival time onto the stack.

4. Return stack size: The final size of the stack represents the number of cars that will reach the destination at or before the first car.

Explanation

The problem revolves around the concept of overtaking. A slower car can't overtake a faster car. Therefore, if a car has a later arrival time and there's a faster car (an earlier arrival time) ahead, the slower car will be overtaken and won't affect the final count. The algorithm cleverly uses a stack to maintain the set of non-overtaken cars that have the greatest impact on determining the number of cars reaching the destination at or before the first one.

Code

import java.util.Arrays;
import java.util.Stack;

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        if (n == 0) return 0;

        double[] arrivalTimes = new double[n];
        for (int i = 0; i < n; i++) {
            arrivalTimes[i] = (double) (target - position[i]) / speed[i];
        }

        int[][] cars = new int[n][2];
        for(int i=0; i<n; i++){
            cars[i][0] = position[i];
            cars[i][1] = speed[i];
        }

        Arrays.sort(cars, (a,b) -> Integer.compare(a[0],b[0]));

        Stack<Double> stack = new Stack<>();
        for (int i = n - 1; i >= 0; i--) {
            if (stack.isEmpty() || arrivalTimes[i] > stack.peek()) {
                stack.push(arrivalTimes[i]);
            }
        }

        return stack.size();
    }
}

Complexity

• Time Complexity: O(N log N), dominated by the sorting step.
• Space Complexity: O(N) in the worst case, to store the arrival times and the stack. The space used by cars array is also O(N).