{x}
blog image

Car Fleet II

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] = [positioni, speedi] represents:

  • positioni is the distance between the ith car and the beginning of the road in meters. It is guaranteed that positioni < positioni+1.
  • speedi is the initial speed of the ith car in meters per second.

For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the slowest car in the fleet.

Return an array answer, where answer[i] is the time, in seconds, at which the ith car collides with the next car, or -1 if the car does not collide with the next car. Answers within 10-5 of the actual answers are accepted.

 

Example 1:

Input: cars = [[1,2],[2,1],[4,3],[7,2]]
Output: [1.00000,-1.00000,3.00000,-1.00000]
Explanation: After exactly one second, the first car will collide with the second car, and form a car fleet with speed 1 m/s. After exactly 3 seconds, the third car will collide with the fourth car, and form a car fleet with speed 2 m/s.

Example 2:

Input: cars = [[3,4],[5,4],[6,3],[9,1]]
Output: [2.00000,1.00000,1.50000,-1.00000]

 

Constraints:

  • 1 <= cars.length <= 105
  • 1 <= positioni, speedi <= 106
  • positioni < positioni+1

Solution Explanation:

This problem asks to find the collision time of cars moving in the same direction. The solution leverages a monotonic stack to efficiently determine collision times.

Approach:

The core idea is to iterate through the cars from right to left. We use a stack to store the indices of cars that might potentially collide with cars encountered later. The stack maintains a monotonically decreasing order of car speeds (from top to bottom).

For each car, we check if it will collide with cars already on the stack. If a collision is detected before a previous collision, the collision time is updated. If no collision occurs with any car on the stack, we simply push the current car's index onto the stack.

Time Complexity: O(N), where N is the number of cars. Each car is pushed onto and popped from the stack at most once.

Space Complexity: O(N) in the worst case, as the stack could hold up to N car indices.

Code Explanation (Python):

class Solution:
    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
        stk = []  # Monotonic stack to store car indices
        n = len(cars)
        ans = [-1] * n  # Initialize collision times to -1 (no collision)
 
        for i in range(n - 1, -1, -1):  # Iterate from right to left
            while stk:  # While stack is not empty
                j = stk[-1]  # Index of the car at the top of the stack
                
                # Check if car i will collide with car j
                if cars[i][1] > cars[j][1]:  # If car i is faster than car j
                    t = (cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1])  # Collision time
                    if ans[j] == -1 or t <= ans[j]:  # If collision time is valid (before previous collision)
                        ans[i] = t  # Update collision time for car i
                        break  # Car i collided, move to the next car
                stk.pop()  # Car j will not collide with car i, pop it from the stack
            stk.append(i)  # Add car i to the stack
        return ans

The Java, C++, and Go code implementations follow a similar logic, adapting the data structures and syntax of their respective languages. The core algorithm remains the same. They all use a stack to efficiently manage car collisions.