Car Fleet

In this problem statement, it is mentioned that the cars are going in a single lane road, this means that if there is a slower ahead of a faster car, then the faster car will join fleet along with the slower car.

So, in this approach, since we dont know which car the is closest one to the destination, whether it is a faster car or slower car, previous position car can only either join fleet along with the closest car to destination or it will form a new fleet. Inorder to achieve this, we are going to sort the position array along with speed as a pair. Then from each position, we will compute, how much time it would take to reach to the destination using remaining distance to destination / speed, After this step, we will store these time values into a stack, before inserting a new time into the stack, we will check if the top element on the stack if greater than current element, that means current car cannot overtake the one in front of it, though it is going at a faster speed, since it is a single lane road, so this car will join the fleet along with the car already going in front of it. So, we will not add this element into the stack, and continue this for all positions, and at the end number of elements we will have it in stack are the total number of fleets.

Let's look at an example, position = [10,8,0,5,3] and speed = [2,4,1,1,3] and target = 12.

• After sorting the position and speed arrays as a pair of numbers, it looks like this [ (10, 2) , (8, 4), (5, 1), (3, 3), (0, 1) ]
• Car at position 10 will reach destination 12 in time = (target - position) / speed = 12 - 10 / 2 = 1. So, we will add this to the stack, so stack = [1].
• Car at position 8 will reach destination 12 in time 12 - 8 / 4 = 1. Now, we will check the the top element in stack, it is 1, same as current, so this car will join the fleet, so we will skip this position.
• Car at position 5 will reach destination 12 in time 12 - 5 / 1 = 7. Now, we will check the the top element in stack, it is 1, it is less than current, so we will add this to the stack, since it wont be able to catch the fleet infront of it. so stack = [1, 7].
• Car at position 3 will reach destination 12 in time 12 - 3 / 3 = 4. Now, we will check the the top element in stack, it is 7, it is greater than current, so we will skip this position, since it will join the fleet infront of it.
• Car at position 0 will reach destination 12 in time 12 - 0 / 1 = 12. Now, we will check the the top element in stack, it is 7, it is less than current, so we will add this to the stack, since it wont be able to catch the fleet infront of it. so stack = [1, 7, 12].
• So, as you can see, there are total 3 fleets in total.

import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;
import java.util.stream.Stream;

public class CarFleet {

    static int carFleetUsingSorting(int target, int[] position, int[] speed) {
        int[][] positionAndSpeedPair = new int[position.length][2];
        for(int i=0; i<position.length; i++) { // position and speed are same length arrays
            positionAndSpeedPair[i][0] = position[i];
            positionAndSpeedPair[i][1] = speed[i];
        }
        // sort based on position, reverse order since we want to sort based on highest position to the lowest position
        Arrays.sort(positionAndSpeedPair, Comparator.comparing(o -> o[0], Comparator.reverseOrder()));
        Stack<Double> stack = new Stack<>();
        Stream.of(positionAndSpeedPair).forEach(pair-> {
            // compute the time it takes to reach destination
            // distance to destination from current position / speed
            double timeToReach = (double)(target - pair[0]) / pair[1];
            if(stack.isEmpty() || timeToReach > stack.peek()) {
                stack.push(timeToReach);
            }
        });
        return stack.size();
    }


    public static void main(String[] args) {
        System.out.println(carFleetUsingSorting(12, new int[]{10,8,0,5,3}, new int[]{2,4,1,1,3}));
    }
}

Complexity Analysis:

Time complexity: All the above operations runs in O(n log n) time since we are sorting the position array, where n is the length of the position array.
Space complexity: O(n) for storing stack elements into stack.

In this approach, we are going to pre-compute time takes for each position to reach destination and store it in a temporary array time. Then, we will loop through from right to left, because the closest position will reach the destinaiton first and it is going to block other cars before that, either they have to join the fleet along with that or form their own fleet.

Let's look at implementation steps with an example, position = [10,8,0,5,3] and speed = [2,4,1,1,3] and target = 12.

• First, declare a temporary array with size as destination, since we are going to pre-compute time it takes to reach destination for every position in position array.
• Compute time[i] = distace[i] / speed[i], so the time array will be [12.0, 0.0, 0.0, 3.0, 0.0, 7.0, 0.0, 0.0, 1.0, 0.0, 1.0, 0.0]
• Car at position 10 will reach destination 12 in time = (target - position) / speed = 12 - 10 / 2 = 1. So, we will add this to the stack, so stack = [1].
• Now, declare two variables previous to store time value, and result to store total number of fleets that it will form.
• Then, loop through time array from right to left and check if the current element is less than or equal to previous, this means that the car on the back is going at fast speed that current one, but the way is a single line road, so this is going to the join the fleet, so we will ignore that element. otherwise, update the previous with current value and also increment result since it will form a new fleet. For example in above array car at position 10 and the car at position 8 are going to form a fleet, and the car at position 5 is going to another fleet since it is greater than all of its right side elements.

public class CarFleet {

    static int carFleet(int target, int[] position, int[] speed) {
        double[] time = new double[target]; // position[i] < target, so length n is good enough
        for(int i=0; i<position.length; i++) {
            time[position[i]] = (double)(target - position[i])/ speed[i];
        }
        int result = 0;
        double prev = 0.0;
        for(int i=time.length-1; i>=0; i--) {
            double current = time[i];
            if(current > prev) {
                prev = current;
                result++;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(carFleet(12, new int[]{10,8,0,5,3}, new int[]{2,4,1,1,3}));

    }
}

Complexity Analysis:

Time complexity: All the above operations runs in O(n) time, where n is the destination.
Space complexity: O(n) for the temporary time array with destination as size.