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 <= 1051 <= positioni, speedi <= 106positioni < positioni+1Problem 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.
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.
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.
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.
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.
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.
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.
| Approach | Complexity |
|---|---|
| Stack-based approach | Time Complexity: O(n). Each car is added and removed from the stack at most once. |
| Formula-based iterative calculation approach | Time Complexity: O(n^2). Each car at position `i` can be compared with all subsequent cars. |
| Default Approach | — |
| 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. |
LeetCode 1776. Car Fleet II | Hard | Weekly Contest 230 | Algorithm Explained | C++ • Cherry Coding [IIT-G] • 4,943 views views
Watch 7 more video solutions →Practice Car Fleet II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor