Watch 8 video solutions for Car Fleet II, a hard level problem involving Array, Math, Stack. This walkthrough by Cherry Coding [IIT-G] has 4,943 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |