1776. Car Fleet II - Solution & Explanation

The 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] = [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

Approach overview

Problem Overview: You are given cars moving along a straight road, each defined by position and speed. When a faster car catches a slower car ahead, they collide and move together as a fleet at the slower speed. For every car, compute the time when it collides with the next car ahead, or return -1 if it never collides.

Approach 1: Event Simulation with Heap (O(n log n))

One way to model the system is as a sequence of collision events. For each adjacent pair of cars, compute the collision time using the formula t = (pos[j] - pos[i]) / (speed[i] - speed[j]) when speed[i] > speed[j]. Store potential events in a priority queue ordered by time. When the earliest collision occurs, merge the cars into a fleet and update neighboring collision events. This approach mirrors a physics-style simulation and is conceptually straightforward, but maintaining the event queue and invalidating outdated events increases complexity. Time complexity is O(n log n) due to heap operations, and space complexity is O(n).

Approach 2: Monotonic Stack with Collision Formula (O(n))

The optimal solution processes cars from right to left and uses a monotonic stack. The stack stores candidate cars ahead that the current car might collide with. For each car, compute the collision time with the top car on the stack using the same relative speed formula. If the current car is slower or would collide after the top car already collides with another fleet, that candidate becomes invalid and gets popped. This pruning step ensures the stack only holds cars that remain valid collision targets.

Each car is pushed and popped at most once, giving O(n) time and O(n) space. The key insight is that collision dependencies only move forward: once a car merges into a fleet, its future behavior is fully determined. Using a stack avoids recomputing events and efficiently filters impossible collisions. The algorithm relies heavily on sequential processing of the array and careful comparison of collision timestamps.

Recommended for interviews: The monotonic stack approach is the expected solution. It reduces the simulation to linear time and demonstrates strong understanding of stack-based pruning and collision timing logic. Explaining the formula for collision time and why outdated candidates are removed from the stack shows deeper reasoning about state changes in dynamic systems.

Approach 1: Stack-based approach

We can process the cars from the back to create a stack-like structure that helps us determine when each car will collide with the car in front of it. By iterating from the last car to the first, we can maintain a stack of cars, managing collisions when the conditions are met.

Python

def getCollisionTimes(cars):
    n = len(cars)
    answer = [-1.0] * n
    stack = []  # stores the idx of cars
    
    for i in range(n-1, -1, -1):
        pos, speed = cars[i]
        
        # Check top of stack car
        while stack:
            j = stack[-1]
            pos_j, speed_j = cars[j]
            
            # if current speed is less than that of the car at stack top,
            # we have a potential collision
            if speed <= speed_j:
                # if speed is not enough to catch up
                stack.pop()
            else:
                # calculate collision time
                collision_time = (pos_j - pos) / (speed - speed_j)
                if answer[j] == -1 or collision_time <= answer[j]:
                    answer[i] = collision_time
                    break
                else:
                    stack.pop()
        
        stack.append(i)
    
    return answer

Java

import java.util.*;
public class CarFleetII {
    public double[] getCollisionTimes(int[][] cars) {
        int n = cars.length;
        double[] answer = new double[n];
        Arrays.fill(answer, -1.0);
        Deque<Integer> stack = new LinkedList<>(); 
        
        for (int i = n - 1; i >= 0; --i) {
            int pos = cars[i][0], speed = cars[i][1];
            
            while (!stack.isEmpty()) {
                int j = stack.peekLast();
                int pos_j = cars[j][0], speed_j = cars[j][1];
                
                if (speed <= speed_j) {
                    stack.pollLast(); 
                } else {
                    double collisionTime = (double)(pos_j - pos) / (speed - speed_j);
                    if (answer[j] == -1 || collisionTime <= answer[j]) {
                        answer[i] = collisionTime;
                        break;
                    } else {
                        stack.pollLast();
                    }
                }
            }
            stack.offerLast(i);
        }
        return answer;
    }
}

C++

#include <vector>
#include <stack>
using namespace std;

vector<double> getCollisionTimes(vector<vector<int>>& cars) {
    int n = cars.size();
    vector<double> answer(n, -1);
    stack<int> stack;

    for (int i = n - 1; i >= 0; --i) {
        int pos = cars[i][0], speed = cars[i][1];

        while (!stack.empty()) {
            int j = stack.top();
            int pos_j = cars[j][0], speed_j = cars[j][1];

            if (speed <= speed_j) {
                stack.pop();
            } else {
                double collisionTime = (double)(pos_j - pos) / (speed - speed_j);
                if (answer[j] == -1 || collisionTime <= answer[j]) {
                    answer[i] = collisionTime;
                    break;
                } else {
                    stack.pop();
                }
            }
        }

        stack.push(i);
    }

    return answer;
}

The function iterates over the cars from right to left. A stack is maintained which will help us evaluate when and if the car at index `i` will hit any other car. The core idea is to calculate collision time whenever necessary and update our answer array accordingly. The collision time calculation is performed based on position differences and speed differentials of cars that are current candidates to collide.

Complexity

Time Complexity: O(n). Each car is added and removed from the stack at most once.
Space Complexity: O(n) due to the stack used for computation.

Try this approach in the editor

Approach 2: Formula-based iterative calculation approach

This approach involves calculating the collision times directly using the positions and speeds. It goes through each car pair iteratively and computes the possible collision times using simple arithmetic calculations. This method eliminates the use of additional data structures but relies on careful calculations.

Python

def calculateCollisionTimes(cars):
    n = len(cars)
    result = [-1.0] * n

    for i in range(n-2, -1, -1):
        pos_i, speed_i = cars[i]
        for j in range(i+1, n):
            pos_j, speed_j = cars[j]
            if speed_i <= speed_j:
                continue
            collision_time = (pos_j - pos_i) / (speed_i - speed_j)
            if result[j] == -1 or collision_time <= result[j]:
                result[i] = collision_time
                break
    return result

Java

public class CarFleetDirect {
    public double[] calculateCollisionTimes(int[][] cars) {
        int n = cars.length;
        double[] result = new double[n];
        for (int i = 0; i < n; i++) result[i] = -1;

        for (int i = n - 2; i >= 0; --i) {
            for (int j = i+1; j < n; ++j) {
                if (cars[i][1] <= cars[j][1])
                    continue;
                double collisionTime = (double)(cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1]);
                if (result[j] == -1 || collisionTime <= result[j]) {
                    result[i] = collisionTime;
                    break;
                }
            }
        }
        return result;
    }
}

C++

#include <vector>

using namespace std;

vector<double> calculateCollisionTimes(const vector<vector<int>>& cars) {
    int n = cars.size();
    vector<double> result(n, -1);

    for (int i = n - 2; i >= 0; --i) {
        for (int j = i + 1; j < n; ++j) {
            if (cars[i][1] <= cars[j][1])
                continue;
            double collisionTime = (double)(cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1]);
            if (result[j] == -1 || collisionTime <= result[j]) {
                result[i] = collisionTime;
                break;
            }
        }
    }

    return result;
}

This function calculates possible collision times by straightforwardly iterating over pairs of cars. It uses direct comparisons and arithmetic to ensure that the collision time is captured based on position differences and their speed ratio. This solution discards combinations where a car cannot catch up.

Complexity

Time Complexity: O(n^2). Each car at position `i` can be compared with all subsequent cars.
Space Complexity: O(1), ignoring the result storage, as no additional space is allocated for temporary data.

Try this approach in the editor

Approach 3: Default Approach

func getCollisionTimes(cars [][]int) []float64 {
	n := len(cars)
	ans := make([]float64, n)
	for i := range ans {
		ans[i] = -1.0
	}
	stk := []int{}
	for i := n - 1; i >= 0; i-- {
		for len(stk) > 0 {
			j := stk[len(stk)-1]
			if cars[i][1] > cars[j][1] {
				t := float64(cars[j][0]-cars[i][0]) / float64(cars[i][1]-cars[j][1])
				if ans[j] < 0 || t <= ans[j] {
					ans[i] = t
					break
				}
			}
			stk = stk[:len(stk)-1]
		}
		stk = append(stk, i)
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Stack-based approach	Time Complexity: O(n). Each car is added and removed from the stack at most once. Space Complexity: O(n) due to the stack used for computation.
Formula-based iterative calculation approach	Time Complexity: O(n^2). Each car at position `i` can be compared with all subsequent cars. Space Complexity: O(1), ignoring the result storage, as no additional space is allocated for temporary data.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Event Simulation with Heap	O(n log n)	O(n)	Useful for understanding the physics-style event model and when modeling collisions explicitly.
Monotonic Stack with Collision Formula	O(n)	O(n)	Optimal solution. Preferred in interviews and competitive programming due to linear complexity.

Frequently asked questions

Is Car Fleet II easy or hard?

Car Fleet II is classified as a Hard problem on LeetCode. The difficulty comes from correctly modeling collision timing and maintaining a stack that removes invalid future collisions.

Car Fleet II Python/Java solution

Typical implementations use a stack of indices and compute collision times with floating point division. The same algorithm works in Python, Java, and C++ with O(n) time complexity and identical logic.

How to solve Car Fleet II in O(n)?

Iterate through cars from right to left and maintain a stack of potential collision targets. For each car, compute collision time using (pos[j] - pos[i]) / (speed[i] - speed[j]). If the target car collides earlier than this time or the current car is slower, remove that candidate and check the next one. This guarantees linear processing.

What is the best approach for Car Fleet II?

The optimal approach uses a monotonic stack processed from right to left. Each car computes its collision time with cars ahead using the relative speed formula and removes invalid candidates from the stack. This pruning guarantees O(n) time and O(n) space complexity.

Is Car Fleet II asked at Google/Amazon/Meta?

Car Fleet II is considered a high-difficulty problem commonly discussed in interview prep for companies like Amazon, Google, and Meta. It tests monotonic stack reasoning, event timing, and careful mathematical modeling of collisions.

What data structure is used in Car Fleet II?

The optimal solution relies on a monotonic stack to track candidate cars ahead. Some conceptual solutions also use a priority queue (heap) to simulate collision events, but the stack approach is more efficient.

What is the time complexity of Car Fleet II?

The optimal monotonic stack solution runs in O(n) time because each car is pushed and popped from the stack at most once. Space complexity is O(n) to store collision times and stack indices.

Car Fleet II solution and explanation

The problem

Approach overview

Approach 1: Stack-based approach

Approach 2: Formula-based iterative calculation approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Car Fleet II solution and explanation

The problem

Approach overview

Approach 1: Stack-based approach

Approach 2: Formula-based iterative calculation approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems