algoadvance

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 arrays 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 can catch up to it and drive bumper to bumper at the same speed. The faster car may slow down to match the slower car’s speed. The distance between these two cars forms a car fleet.

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

Example

Input: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
Output: 3
Explanation:
The cars starting at positions 10 and 8 are in forming a fleet, their arrival times at the destination are 1, 1.
The car starting at position 5 forms a fleet.
The cars starting at positions 0 and 3 are in forming a fleet, their arrival times at the destination are 8, 3.

Clarifying Questions

  1. Order of Input Arrays: Are position and speed aligned such that position[i] and speed[i] correspond to the same car?
    • Yes.
  2. Constraints: What constraints should I consider regarding the length of arrays and the values within them?
    • Constraints are as follows:
      • n == position.length == speed.length
      • 1 <= n <= 10^4
      • 0 < position[i] < target <= 10^6
      • 0 < speed[i] <= 10^6
  3. Behavior of the Cars: Is it correct that a car cannot pass another and will match the slower car’s speed if caught up?
    • Yes, if a car catches up with another, it will form a fleet and match the slower car’s speed.

With these clarifications, let’s proceed with the solution.

Strategy

  1. Calculate Time to Reach Destination:
    • For each car, calculate the time it will take to reach the target.
    • Formula: (target - position[i]) / speed[i].
  2. Sort Cars by Position:
    • The cars are processed from the farthest to the closest to the target. This ensures that we identify when a fleet is formed properly.
  3. Track Fleets:
    • Use a stack to keep track of fleet times.
    • Iterate over the sorted cars; if the current car’s time is greater than the fleet time at the top of the stack, it forms a new fleet. Otherwise, it becomes part of the existing fleet.

Code

def carFleet(target, position, speed):
    cars = sorted(zip(position, speed))
    fleets = 0
    time_to_reach = [(target - p) / s for p, s in cars]
    
    i = len(time_to_reach) - 1
    while i >= 0:
        fleets += 1
        lead_time = time_to_reach[i]
        while i >= 0 and time_to_reach[i] <= lead_time:
            i -= 1
    
    return fleets

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

Time Complexity

Overall, the time complexity is O(n log n) due to the sorting step being the most computationally expensive operation.

This should adequately solve the problem within given constraints.

Try our interview co-pilot at AlgoAdvance.com