# Car Fleet II
**Difficulty:** HARD
[External](https://leetcode.com/problems/car-fleet-ii)
Canonical: https://scaleengineer.com/dsa/problems/car-fleet-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array, Stack, Heap (Priority Queue), Monotonic Stack
---
## Problem
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`

# Approaches
## Brute Force with Collision Chain Check
This approach iterates through each car from right to left. For each car `i`, it checks every car `j` in front of it to find the earliest possible collision time. A collision between car `i` and car `j` is only considered valid if car `j` does not collide with another car before car `i` can reach it. Since we process cars from right to left, the collision time for car `j` is already computed, which simplifies the logic.
**Time:** O(N^2) due to the nested loops. For each car, we potentially iterate through all cars in front of it. · **Space:** O(N) to store the `answer` array.
**Pros:** Relatively straightforward to conceptualize compared to more optimized solutions.; Correctly handles the chain reaction of collisions by using previously computed results from the right-to-left scan.
**Cons:** The O(N^2) time complexity is too slow for the given constraints (`n <= 10^5`) and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The core idea is to solve the problem for each car `i` by looking ahead at all cars `j > i`. We iterate from the second to last car backwards to the first car. For each car `i`, we iterate forward from `i+1` to the end. We calculate the time `t_ij` for `i` to catch `j`. A crucial observation is that this collision is only the *first* collision for `i` if two conditions are met: 1) `i` does not collide with any car `k` between `i` and `j` earlier than `t_ij`, and 2) car `j` does not collide with any car ahead of it before `t_ij`. The first condition is handled by finding the minimum time among all valid `t_ij`. The second condition is handled by using the pre-computed `answer[j]`. If `t_ij` is greater than `answer[j]`, it means `j` is already part of a fleet by the time `i` gets there, so `i` cannot collide with `j` directly.

```java
import java.util.Arrays;

class Solution {
    public double[] getCollisionTimes(int[][] cars) {
        int n = cars.length;
        double[] answer = new double[n];
        Arrays.fill(answer, -1.0);

        for (int i = n - 2; i >= 0; i--) {
            double minTime = -1.0;
            for (int j = i + 1; j < n; j++) {
                // If car i is not faster than car j, it can't catch up
                if (cars[i][1] <= cars[j][1]) {
                    continue;
                }

                // Calculate time to collide
                double timeToCollide = (double)(cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1]);

                // Check if car j collides with another car before car i collides with j
                if (answer[j] != -1 && timeToCollide >= answer[j]) {
                    continue;
                }
                
                // If this is the first possible collision or an earlier one
                if (minTime == -1.0 || timeToCollide < minTime) {
                    minTime = timeToCollide;
                }
            }
            answer[i] = minTime;
        }
        return answer;
    }
}
```
### Algorithm
*   Initialize an `answer` array of size `n` with `-1.0`.
*   Iterate through the cars from `i = n - 2` down to `0`.
*   For each car `i`, initialize its minimum collision time `min_time` to a sentinel value like -1.
*   Iterate through the cars `j` from `i + 1` to `n - 1`.
*   If car `i` is slower than or has the same speed as car `j` (`cars[i][1] <= cars[j][1]`), it can never catch up, so we continue to the next `j`.
*   Otherwise, calculate the time `t_ij` for car `i` to collide with car `j`: `t_ij = (pos_j - pos_i) / (speed_i - speed_j)`.
*   This collision is only possible if car `j` doesn't collide with another car first. The time for car `j` to collide is `answer[j]`, which is already computed.
*   If `answer[j]` is not `-1` and `t_ij` is greater than or equal to `answer[j]`, it means car `j` merges into a fleet before car `i` can hit it. So, this is not a direct collision with `j`. We ignore this `t_ij` and continue.
*   If the collision is possible (`answer[j] == -1` or `t_ij < answer[j]`), then `t_ij` is a candidate for the collision time of car `i`. We update `min_time` to be the minimum of itself and `t_ij`.
*   After checking all `j`, if `min_time` was updated, `answer[i]` is set to `min_time`. Otherwise, it remains `-1`.

## Monotonic Stack
A more efficient approach uses a monotonic stack. By processing cars from right to left, we can maintain a stack of car indices that are potential collision targets. The stack helps to quickly discard cars that are either too fast to be caught or will be involved in an earlier collision, thus avoiding the O(N^2) search of the brute-force method. This optimization reduces the time complexity to linear.
**Time:** O(N). Each car index is pushed onto and popped from the stack at most once. The main loop runs `N` times, and the inner while loop operations are amortized O(1) over all iterations. · **Space:** O(N). In the worst case, the stack can hold all `N` indices. We also need O(N) space for the `answer` array.
**Pros:** Highly efficient with linear time complexity, which easily passes the given constraints.; Elegantly handles the complex collision logic by maintaining a monotonic stack of candidates.
**Cons:** The logic can be less intuitive to grasp compared to the brute-force approach, particularly the conditions for popping from the stack.
### Explanation
This approach iterates from right to left, calculating the collision time for each car. A stack is used to keep track of the indices of cars ahead that are potential collision candidates. When considering car `i`, we compare it with the car `j` at the top of the stack.

If car `i` is slower than or has the same speed as car `j`, `i` can't catch `j`. Since the stack maintains cars in increasing order of position, `i` also can't catch any car shielded by `j`. Thus, `j` is popped.

If car `i` is faster than `j`, we calculate the time `t_ij` for them to collide. We then check if this collision is realistic. If car `j` is already set to collide with another car at a time `answer[j]` that is earlier than `t_ij`, then car `i` won't collide with `j` but with the fleet `j` forms. In this case, `j` is not the direct target, so we pop it and check the next car on the stack. 

If `i` can collide with `j` (either because `j` never collides or `i` reaches it first), we've found the answer for `i`, record the time, and break the inner loop. Finally, we push `i` onto the stack, making it a potential target for cars behind it.

```java
import java.util.Stack;

class Solution {
    public double[] getCollisionTimes(int[][] cars) {
        int n = cars.length;
        double[] answer = new double[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = n - 1; i >= 0; i--) {
            answer[i] = -1.0;
            int pos_i = cars[i][0];
            int speed_i = cars[i][1];

            while (!stack.isEmpty()) {
                int j = stack.peek();
                int pos_j = cars[j][0];
                int speed_j = cars[j][1];

                // If car i is slower or same speed as car j, i can't catch j.
                // Since cars on stack are ordered by position, i also can't catch
                // any car behind j on the road. Pop j.
                if (speed_i <= speed_j) {
                    stack.pop();
                    continue;
                }

                // If car i is faster, calculate collision time.
                double timeToCollide = (double)(pos_j - pos_i) / (speed_i - speed_j);

                // If j collides with its next car sooner than i collides with j,
                // then i will actually collide with the fleet j forms.
                // So, j is not the direct collision target. Pop j and check the next car.
                if (answer[j] != -1 && timeToCollide >= answer[j]) {
                    stack.pop();
                    continue;
                }
                
                // Otherwise, i collides with j. This is the answer for i.
                answer[i] = timeToCollide;
                break;
            }
            stack.push(i);
        }
        return answer;
    }
}
```
### Algorithm
*   Initialize an `answer` array of size `n` with `-1.0`.
*   Initialize an empty stack to store car indices.
*   Iterate through the cars from `i = n - 1` down to `0`.
*   For the current car `i`, we look at the cars on the stack. The stack will hold indices of cars `j` such that `pos_i < pos_j`.
*   While the stack is not empty, let `j` be the index at the top of the stack.
    *   **Case 1: Car `i` is slower or same speed.** If `cars[i][1] <= cars[j][1]`, car `i` can never catch car `j`. Since `j` is the closest car on the stack, `i` also can't catch any car `k` that is behind `j` on the road (and thus below `j` in the stack). Car `i` now acts as a new 'slow car barrier' for any cars behind it. So, we pop `j` from the stack as it's no longer a candidate for `i` or any car behind `i`.
    *   **Case 2: Car `i` is faster.** If `cars[i][1] > cars[j][1]`, car `i` can potentially collide with car `j`. Calculate the collision time `t_ij`.
        *   We must check if `j` collides with its own target before `i` reaches it. The collision time for `j` is `answer[j]`, which we have already computed.
        *   If `answer[j]` is not -1 and `t_ij >= answer[j]`, it means `j` merges into a fleet before `i` can collide with it. From `i`'s perspective, `j` is no longer a direct target. The real target is the fleet `j` joins. This is equivalent to ignoring `j` and considering the next car on the stack. So, we pop `j`.
        *   If `answer[j] == -1` or `t_ij < answer[j]`, then `i` will successfully collide with `j`. This is the first car `i` will hit. We set `answer[i] = t_ij` and break the while loop.
*   If the while loop finishes and the stack is empty, it means car `i` will not collide with any car in front of it. `answer[i]` remains `-1.0`.
*   Push the current index `i` onto the stack. It becomes a potential collision target for the cars behind it.

# Solutions
### Java

```java
class Solution {
public
  double[] getCollisionTimes(int[][] cars) {
    int n = cars.length;
    double[] ans = new double[n];
    Arrays.fill(ans, -1.0);
    Deque<Integer> stk = new ArrayDeque<>();
    for (int i = n - 1; i >= 0; --i) {
      while (!stk.isEmpty()) {
        int j = stk.peek();
        if (cars[i][1] > cars[j][1]) {
          double t =
              (cars[j][0] - cars[i][0]) * 1.0 / (cars[i][1] - cars[j][1]);
          if (ans[j] < 0 || t <= ans[j]) {
            ans[i] = t;
            break;
          }
        }
        stk.pop();
      }
      stk.push(i);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<double> getCollisionTimes(vector<vector<int>> &cars) {
    int n = cars.size();
    vector<double> ans(n, -1.0);
    stack<int> stk;
    for (int i = n - 1; ~i; --i) {
      while (stk.size()) {
        int j = stk.top();
        if (cars[i][1] > cars[j][1]) {
          double t =
              (cars[j][0] - cars[i][0]) * 1.0 / (cars[i][1] - cars[j][1]);
          if (ans[j] < 0 || t <= ans[j]) {
            ans[i] = t;
            break;
          }
        }
        stk.pop();
      }
      stk.push(i);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]: stk = [] n = len(cars) ans = [- 1] * n for i in range(n - 1, - 1, - 1): while stk: j = stk[- 1] if cars[i][1] > cars[j][1]: t = (cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1]) if ans[j] == - 1 or t <= ans[j]: ans[i] = t break stk . pop() stk . append(i) return ans

```