Car Fleet

Medium

Google

7 views

Topics:

ArraysStacksGreedy Algorithms

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.

You are given two integer array position and speed, both of length n, where position[i] is the starting mile of the ith car and speed[i] is the speed of the ith car in miles per hour.

A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car.

A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet.

If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet.

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

Example 1:

target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]

Output: 3

Example 2:

target = 10, position = [3], speed = [3]

Output: 1

Example 3:

target = 100, position = [0,2,4], speed = [4,2,1]

Output: 1

Car Fleet

Medium

Google

7 views

Topics:

ArraysStacksGreedy Algorithms

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.

You are given two integer array position and speed, both of length n, where position[i] is the starting mile of the ith car and speed[i] is the speed of the ith car in miles per hour.

A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car.

A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet.

If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet.

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

Example 1:

target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]

Output: 3

Example 2:

target = 10, position = [3], speed = [3]

Output: 1

Example 3:

target = 100, position = [0,2,4], speed = [4,2,1]

Output: 1

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the positions and speeds be floats or are they always integers?
Is it possible for two or more cars to start at the same position?
If a car reaches the target before another, does it become part of the same fleet?
If no cars reach the target, should I return 0, or is there another specific value expected?
Is the target position always greater than the starting positions of the cars?

Brute Force Solution

Approach

The brute force approach to the car fleet problem is like watching each car individually and tracking how it moves. We simulate the entire journey for every car to see when and if they form a fleet. This involves calculating each car's arrival time at the destination based on its initial position and speed.

Here's how the algorithm would work step-by-step:

For each car, calculate the time it would take to reach the target if it maintained its initial speed.
Imagine all the cars starting at the same time. The cars that reach the target at or before another car form a fleet with that car.
Go through the cars from the back to the front. If a car catches up to the car in front, they are part of the same fleet.
When a car does not catch up with the car in front, it forms a new fleet.
Count the total number of fleets formed. This is the final answer.

Code Implementation

def car_fleet_brute_force(target, position, speed):
    car_count = len(position)

    arrival_times = []
    for i in range(car_count):
        arrival_time = (target - position[i]) / speed[i]
        arrival_times.append(arrival_time)

    # Sort cars based on their position
    car_positions_and_times = sorted(zip(position, arrival_times))

    fleets = 0
    # If there are no cars, there are no fleets
    if not car_positions_and_times:
        return 0

    fleets = 1
    leader_position, leader_arrival_time = car_positions_and_times[-1]

    # Iterate from the back to the front
    for i in range(car_count - 2, -1, -1):
        current_position, current_arrival_time = car_positions_and_times[i]

        # Check if the current car catches up to the leader car
        if current_arrival_time > leader_arrival_time:
            # If it does not catch up, it forms a new fleet
            fleets += 1
            leader_position, leader_arrival_time = current_position, current_arrival_time

    return fleets

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n cars. For each car, it compares its arrival time to the arrival times of all the cars in front of it, which takes up to n comparisons in the worst case. Therefore, the nested loop structure results in roughly n * n comparisons, leading to approximately n * n/2 operations. This simplifies to a time complexity of O(n²).

Space Complexity

O(N) – The space complexity is determined by the need to store the time it takes each car to reach the target. This involves calculating and implicitly storing these times, conceptually associating each car with its arrival time. Therefore, we are using space proportional to the number of cars (N) to store these arrival times, either directly or indirectly. This results in an auxiliary space complexity of O(N).

Optimal Solution

Approach

The key to solving the car fleet problem efficiently is to figure out which cars will form a fleet and when they will arrive. The cars that arrive at the destination together are the ones that form a fleet. We can determine fleet formation by calculating arrival times.

Here's how the algorithm would work step-by-step:

First, organize the cars by their starting position from closest to the destination to farthest from the destination.
Calculate the time it will take each car to reach the destination.
Start with the car furthest from the destination. This car may form a fleet or it might be the only member of a fleet.
Now consider the car immediately behind the first car. If this car arrives at the destination at the same time or earlier than the first car, then they will form a fleet and the slower arrival time of the lead car will determine the fleet's arrival time.
If the car behind arrives later, then it will form its own separate fleet.
Continue this process, comparing each car's arrival time to the arrival time of the car ahead of it (or the existing fleet ahead of it).
Each time you encounter a car that arrives later than the fleet ahead of it, it forms a new fleet.
The number of fleets is simply the number of times a car does not join a pre-existing fleet, but instead starts a new one.

Code Implementation

def carFleet(target, position, speed):
    cars = sorted(zip(position, speed))
    arrival_times = [(target - position) / speed for position, speed in cars]
    
    number_of_fleets = 0
    max_arrival_time = 0.0
    
    for arrival_time in reversed(arrival_times):
        # If current car arrives later, it forms a new fleet.
        if arrival_time > max_arrival_time:
            number_of_fleets += 1
            max_arrival_time = arrival_time

    return number_of_fleets

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this solution is sorting the cars based on their starting positions, which takes O(n log n) time. After sorting, the algorithm iterates through the sorted cars once, calculating arrival times and comparing them. This linear iteration takes O(n) time. Since O(n log n) grows faster than O(n), the overall time complexity is determined by the sorting step. Therefore, the time complexity is O(n log n).

Space Complexity

O(N) – The primary space complexity comes from organizing the cars by their starting position, which implicitly means creating a data structure, such as an array or list of tuples, where each tuple contains the car's position and speed. Since we store information for each of the N cars, this results in an auxiliary data structure of size N. No other significant data structures are used beyond a few constant space variables, therefore the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty positions or speeds array	Return 0 immediately as no cars exist, thus no car fleets.
Positions and speeds arrays have different lengths	Throw an IllegalArgumentException to signal invalid input.
Single car; positions array of size 1	Return 1, as a single car trivially forms a fleet.
Cars with the same position but different speeds	The faster car will eventually overtake the slower car and merge into the fleet, which needs accurate calculation of arrival times.
Cars with very large positions and speeds (close to Integer.MAX_VALUE) causing overflow during time calculation	Use long to store intermediate time calculations to prevent integer overflow.
Cars with speed of 0.0 (zero speed)	Consider these cars as never reaching the target, and exclude them from fleet formation calculation or throw an IllegalArgumentException if zero speed is invalid.
Cars already at the target position	Treat these cars as arriving immediately (time = 0) and factor them into the fleet count.
Target position is smaller than some car positions (negative relative distance)	Exclude these cars as they are moving away from the target, or throw an IllegalArgumentException if invalid.