We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Car Fleet

Number: 883

Difficulty: Medium

Paid? No

Companies: Google, Infosys, Microsoft, Amazon, Bloomberg, Apple, TikTok, GE Healthcare, Nutanix

Problem Description

There are n cars on a road, each at a unique starting mile and with a given speed. All cars are headed toward a target destination. A car cannot overtake another but can catch up and join the car fleet. A car fleet is defined as one or more cars traveling together at the minimum speed amongst them. When a faster car catches up to a slower car (or fleet) before reaching the target, they merge into a single fleet. The goal is to determine the number of distinct car fleets that will arrive at the destination.

Key Insights

  • Since cars cannot pass each other, the relative order (by starting position) is maintained.
  • Sorting the cars based on their starting positions (descending order) helps to simulate the catching-up process.
  • Computing the time each car takes to reach the target is critical.
  • Compare the current car’s time to the time of the fleet ahead: if it takes longer, it forms a new fleet; otherwise, it gets merged.
  • A stack-like approach (tracking the slowest arrival time seen so far) reduces the problem to a single pass after sorting.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting step. Space Complexity: O(n) for storing the computed times and sorted car information.

Solution

The solution involves sorting the cars by their starting positions in descending order so that we process the cars from nearest to the target to farthest. For each car, calculate the time to reach the target using the formula (target - position) / speed. As we iterate:

  • If a car’s time is greater than the slowest time encountered (tracked by a variable or stack), it cannot catch up to the fleet ahead and forms a new fleet.
  • Otherwise, it merges into the current fleet. This approach ensures that we count each distinct fleet accurately with a single pass through the sorted list.

Code Solutions

# Python implementation of Car Fleet
def carFleet(target, position, speed):
    # Pair up position and speed and sort by starting position in descending order.
    cars = sorted(zip(position, speed), key=lambda car: car[0], reverse=True)
    
    fleets = 0         # Count of car fleets
    last_time = 0.0    # Time taken by the last fleet to reach the target
    
    # Process each car from closest to farthest from the target.
    for pos, spd in cars:
        # Calculate time for this car to reach the target
        time = (target - pos) / spd
        
        # If this car takes longer than the last fleet time, it starts a new fleet.
        if time > last_time:
            fleets += 1
            last_time = time  # Update the last fleet time with this car's time
            
    return fleets

# Example usage:
# target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
# print(carFleet(12, [10,8,0,5,3], [2,4,1,1,3]))  # Output: 3
← Back to All Questions