NeetCode 150: Car Fleet

Table of contents

The Problem

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 array position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).

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. The distance between these two cars is ignored (i.e., they are assumed to have the same position).

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

Return the number of car fleets that will arrive at the destination.

The Approach

The goal is to determine’s each car’s time to reach target. We first need to add each car’s respective position & speed into a Map to form a pair (a relation between them). Then, these keys are sorted.

This is becuase the cars need to be inserted in the order of position (highest first) into a Stack. The latest car added is then compared to the current log of all possible fleets to check if it can join or create a new fleet.

My Solution

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        // Create a Map to store car data (position & speed) so that it can be sorted by position.
        // Create a Stack to store the addition of each cars' travelValue (time to reach target) to find total number of fleets.
        Map<Integer, Integer> allCars = new HashMap<Integer, Integer>();
        Stack<Float> carsTracker = new Stack<Float>();

        // Changed to float for decimal values in comparison.
        float targetFloat = (float) target;

        for (int i = 0; i < position.length; i++) {
            allCars.put(position[i], speed[i]);
        }
        
        // Add all keys to a List to be sorted (unable to natively sort by keys in a Java HashMap).
        List<Integer> sortedPositions = new ArrayList<Integer>(allCars.keySet());
        Collections.sort(sortedPositions);
        
        // In order of position, determine the timeTakenToReachTarget (time taken to reach target) of the respective car.
        // If the current timeTakenToReachTarget is smaller than the top of the stack, it means that the this car will catch the 
        // top car and both cars will assume the current (slower) top car's speed (merged into 1 fleet) > No need to add the
        // current timeTakenToReachTarget & keep current top car (in the stack).
        //
        // Else, this means that the two cars will never catch each other and will be separate fleets > Add to stack.
        for (int i = (position.length - 1); i >= 0; i--) {
            int currentPositionValue = sortedPositions.get(i);
            Float timeTakenToReachTarget = (targetFloat - currentPositionValue) / allCars.get(currentPositionValue);

            if ((!(carsTracker.isEmpty())) && (timeTakenToReachTarget <= carsTracker.peek())) {
                // When cars catch each other, they follow the slower speed, so there is no need to push the new value.
                continue;
            } else {
                carsTracker.push(timeTakenToReachTarget);
            }
        }
        // The size of the stack will be the total number of fleets as each fleet is unable to catch the following fleet.
        return carsTracker.size();
    }
}

We first initialize;

• allCars: A Map that keep track of the position & speed pair of each car.
• carsTracker: A Stack where each fleet is logged.

We then loop over all the elements (i.e. cars) in position & adding its respective speed (key-value pair) to to allCars. The keys (i.e. position) are added to an ArrayList & is then sorted (no native sort method for Map).

We then loop over all the keys in reverse (as each car needs to be compared to the car ahead), calculating the timeTakenToReachTarget which is the division of the distance needed to travel and its respective speed.

Then, timeTakenToReachTarget (provided thatcarsTracker is not empty) is compared to the value at the top of the stack;

• timeTakenToReachTarget <= carsTracker.peek(): This means that the car will catch this fleet & match the speed of this fleet. No insertion is required.
• timeTakenToReachTarget > carsTracker.peek(): This means that the car will never catch the fleet (i.e. the fleet “ahead”). A new fleet is formed & it is inserted into carsTracker.

At the end, the size of carsTracker is returned, which logs all the fleets.