Car Fleet II

Hard

#1626Time: 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.

Patterns

Math

Data structures

Array Stack Heap (Priority Queue)Monotonic Stack

Prompt

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:

position_i is the distance between the i^th car and the beginning of the road in meters. It is guaranteed that position_i < position_i+1.
speed_i is the initial speed of the i^th 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 i^th 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 <= 10⁵
1 <= position_i, speed_i <= 10⁶
position_i < position_i+1

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.Arrays;2 3class Solution {4    public double[] getCollisionTimes(int[][] cars) {5        int n = cars.length;6        double[] answer = new double[n];7        Arrays.fill(answer, -1.0);8 9        for (int i = n - 2; i >= 0; i--) {10            double minTime = -1.0;11            for (int j = i + 1; j < n; j++) {12                // If car i is not faster than car j, it can't catch up13                if (cars[i][1] <= cars[j][1]) {14                    continue;15                }16 17                // Calculate time to collide18                double timeToCollide = (double)(cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1]);19 20                // Check if car j collides with another car before car i collides with j21                if (answer[j] != -1 && timeToCollide >= answer[j]) {22                    continue;23                }24                25                // If this is the first possible collision or an earlier one26                if (minTime == -1.0 || timeToCollide < minTime) {27                    minTime = timeToCollide;28                }29            }30            answer[i] = minTime;31        }32        return answer;33    }34}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.Stack;2 3class Solution {4    public double[] getCollisionTimes(int[][] cars) {5        int n = cars.length;6        double[] answer = new double[n];7        Stack<Integer> stack = new Stack<>();8 9        for (int i = n - 1; i >= 0; i--) {10            answer[i] = -1.0;11            int pos_i = cars[i][0];12            int speed_i = cars[i][1];13 14            while (!stack.isEmpty()) {15                int j = stack.peek();16                int pos_j = cars[j][0];17                int speed_j = cars[j][1];18 19                // If car i is slower or same speed as car j, i can't catch j.20                // Since cars on stack are ordered by position, i also can't catch21                // any car behind j on the road. Pop j.22                if (speed_i <= speed_j) {23                    stack.pop();24                    continue;25                }26 27                // If car i is faster, calculate collision time.28                double timeToCollide = (double)(pos_j - pos_i) / (speed_i - speed_j);29 30                // If j collides with its next car sooner than i collides with j,31                // then i will actually collide with the fleet j forms.32                // So, j is not the direct collision target. Pop j and check the next car.33                if (answer[j] != -1 && timeToCollide >= answer[j]) {34                    stack.pop();35                    continue;36                }37                38                // Otherwise, i collides with j. This is the answer for i.39                answer[i] = timeToCollide;40                break;41            }42            stack.push(i);43        }44        return answer;45    }46}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  double[] getCollisionTimes(int[][] cars) {4    int n = cars.length;5    double[] ans = new double[n];6    Arrays.fill(ans, -1.0);7    Deque<Integer> stk = new ArrayDeque<>();8    for (int i = n - 1; i >= 0; --i) {9      while (!stk.isEmpty()) {10        int j = stk.peek();11        if (cars[i][1] > cars[j][1]) {12          double t =13              (cars[j][0] - cars[i][0]) * 1.0 / (cars[i][1] - cars[j][1]);14          if (ans[j] < 0 || t <= ans[j]) {15            ans[i] = t;16            break;17          }18        }19        stk.pop();20      }21      stk.push(i);22    }23    return ans;24  }25}

1class Solution {2public:3  vector<double> getCollisionTimes(vector<vector<int>> &cars) {4    int n = cars.size();5    vector<double> ans(n, -1.0);6    stack<int> stk;7    for (int i = n - 1; ~i; --i) {8      while (stk.size()) {9        int j = stk.top();10        if (cars[i][1] > cars[j][1]) {11          double t =12              (cars[j][0] - cars[i][0]) * 1.0 / (cars[i][1] - cars[j][1]);13          if (ans[j] < 0 || t <= ans[j]) {14            ans[i] = t;15            break;16          }17        }18        stk.pop();19      }20      stk.push(i);21    }22    return ans;23  }24};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem