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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Car Fleet II

Difficulty: Hard

Problem Description

There are n cars traveling at different speeds in the same direction along a one-lane road. You are given an array cars of length n, where cars[i] = [position_i, speed_i] represents the distance between the i-th car and the beginning of the road in meters and the initial speed of the i-th car in meters per second. The task is to return an array answer, where answer[i] is the time, in seconds, at which the i-th car collides with the next car, or -1 if the car does not collide with the next car.

Key Insights

  • Cars with higher speeds that are positioned behind slower cars may collide with them.
  • When a collision happens, the resulting car fleet travels at the speed of the slowest car in that fleet.
  • The time to collision can be calculated using the formula: time = (position[j] - position[i]) / (speed[i] - speed[j]) for cars i and j, where speed[i] > speed[j].
  • A stack can be used to maintain the collision times as we iterate from the back of the cars array to the front.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a stack to keep track of the collision times for the cars. We iterate through the list of cars from the last car to the first car. For each car, we check if it will collide with the next car in front. If it does, we calculate the time of collision and store it in the stack. If it does not collide, we store -1. Finally, we reverse the stack to get the correct order of collision times.

Code Solutions

def getCollisionTimes(cars):
    n = len(cars)
    answer = [-1] * n
    stack = []
    
    for i in range(n - 1, -1, -1):
        while stack:
            j = stack[-1]
            time_to_collision = (cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1])
            if time_to_collision <= 0:
                stack.pop()
            else:
                answer[i] = time_to_collision
                stack.append(i)
                break
        stack.append(i)
    
    return answer
← Back to All Questions