Skip to main content
Talentd

Car Fleet II - Solution & Explanation

HardArrayMathStackHeap (Priority Queue)11 min readAsked at: Amazon, Microsoft, Google
Practice this problem

Problem Statement

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

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.

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.

Code

PythonJavaC++

Python

Java

C++

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.

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.

Code

PythonJavaC++

Python

Java

C++

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

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

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

Video Solution

LeetCode 1776. Car Fleet II | Hard | Weekly Contest 230 | Algorithm Explained | C++ • Cherry Coding [IIT-G] • 5,149 views views

Watch 7 more video solutions →

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.

Ready to solve this problem?

Practice Car Fleet II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Car Fleet

Next

Count Collisions on a Road