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 II

Number: 1902

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given n cars moving along a one-lane road, each car has an initial position and speed. When one car catches up to another, they collide and form a fleet that moves at the slowest car’s speed. The task is to determine, for each car, the time at which it will collide with the next car (or fleet) ahead. If a car never collides, its collision time should be -1.

Key Insights

  • Process the cars from rightmost (leading) to leftmost since the collision dynamics depend on the car in front.
  • Use a monotonic stack to keep track of candidate cars/fleets that could be collided with.
  • The collision time between car i and a car j ahead (if i is faster than j) is calculated using (position[j] - position[i]) / (speed[i] - speed[j]).
  • Ensure that if a collision time computed is greater than an already determined collision time for the car ahead, then that car would have already changed speed (or merged into a fleet), so the current car’s collision must be recalculated with the next candidate.

Space and Time Complexity

Time Complexity: O(n) – Each car is processed once and while loops pop from the stack at most once per car. Space Complexity: O(n) – The stack may store up to n indices.

Solution

The solution leverages a monotonic stack that holds indices of cars ahead (from right to left) with potential collision times. By iterating from the last car backward, we compute the collision time for the current car with the car indicated at the top of the stack. If the current car cannot catch up or its computed collision time occurs after the car ahead has already merged into another fleet, we remove that car from the stack and evaluate the next candidate. Finally, we store the collision time or -1 if no collision will occur and push the current car onto the stack.

Code Solutions

def getCollisionTimes(cars):
    n = len(cars)
    result = [-1.0] * n
    stack = []  # Stack to hold indices of cars/fleets ahead
    
    # Process from the last car to the first car
    for i in range(n - 1, -1, -1):
        pos, speed = cars[i]
        # Determine collision time with a car/fleet ahead.
        while stack:
            # If the current car is slower or equal in speed, it will never catch up.
            if speed <= cars[stack[-1]][1]:
                stack.pop()
            else:
                # Compute potential collision time.
                t = (cars[stack[-1]][0] - pos) / (speed - cars[stack[-1]][1])
                # If the car ahead never collides or if the collision happens before the car ahead merges
                if result[stack[-1]] == -1 or t <= result[stack[-1]]:
                    break
                else:
                    stack.pop()
        if stack:
            result[i] = (cars[stack[-1]][0] - pos) / (speed - cars[stack[-1]][1])
        stack.append(i)
    return result

# Example usage:
cars = [[1, 2], [2, 1], [4, 3], [7, 2]]
print(getCollisionTimes(cars))
← Back to All Questions