LeetCode 1776 - Car Fleet II

LeetCode Problem 1776

Difficulty: 🔴 Hard
Topics: Array, Math, Stack, Heap (Priority Queue), Monotonic Stack

Solution

Problem Understanding

The problem is asking us to compute the time at which each car in a line of cars collides with the car immediately in front of it, or return -1 if it never collides. Each car is represented by its position and speed. The cars are initially sorted by position in increasing order, and the speeds can vary. A collision occurs when two cars occupy the same position. After a collision, the cars move together as a fleet at the slower speed of the two cars involved.

The input cars is a list of [position, speed] pairs, where position is strictly increasing. This guarantees that no two cars start at the same location. The output is an array answer of the same length, where answer[i] is the time in seconds when the i-th car collides with the car directly ahead of it, or -1 if it never collides. The answers should be accurate within 10^-5.

Important constraints and observations:

• Up to 10^5 cars, so naive O(n²) approaches will be too slow.
• Positions and speeds are positive integers up to 10^6.
• Cars are already sorted by position, simplifying our traversal logic.
• Collisions propagate: once a fleet is formed, the fleet’s speed is the minimum of the constituent cars’ speeds. Subsequent cars may collide with this fleet.

Key edge cases:

1. A car is faster than the one ahead and will eventually collide.
2. A car is slower than the one ahead and will never collide.
3. A car collides with a fleet rather than a single car.
4. Only one car exists.

Approaches

The brute-force approach would iterate over each car, calculate the time it takes to collide with every car in front until a collision is found, and record the first collision. While correct, this is O(n²) due to nested loops and is infeasible for n = 10^5.

The optimal approach leverages a monotonic stack to process cars from the back to the front. By tracking potential collisions ahead, we only need to check the next car/fleet for collision time. If the next car/fleet is faster or collides after our current car would reach it, we skip it. This guarantees O(n) time complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Compute collision times for each car by checking all cars in front. Too slow for large inputs.
Optimal	O(n)	O(n)	Monotonic stack tracks cars/fleets from back to front, computing collision times efficiently.

Algorithm Walkthrough

1. Initialize a stack to track indices of cars from back to front. This stack will represent cars that the current car may collide with.

2. Initialize the answer array to -1 for all cars, representing no collision by default.

3. Iterate through the cars from right to left. For each car:

4. While the stack is not empty, compute the collision time with the car at the top of the stack using (position[next] - position[current]) / (speed[current] - speed[next]).

5. If the current car is slower than the car ahead or will collide after the car ahead collides with another car, pop the stack and check the next car.

6. If a valid collision time exists, store it in answer[current].

7. Push the current car index onto the stack.

8. Return the answer array.

Why it works: By processing from back to front and maintaining a stack of potential collisions, we ensure that each car only checks relevant cars ahead. The stack effectively keeps cars in a "monotonic order of potential collision times," ensuring O(n) complexity.

Python Solution

from typing import List

class Solution:
    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
        n = len(cars)
        answer = [-1.0] * n
        stack = []  # stores indices of cars that are potential collisions
        
        for i in range(n - 1, -1, -1):
            position_i, speed_i = cars[i]
            
            while stack:
                j = stack[-1]
                position_j, speed_j = cars[j]
                
                if speed_i <= speed_j:
                    stack.pop()
                    continue
                
                time_to_collide = (position_j - position_i) / (speed_i - speed_j)
                
                if answer[j] != -1 and time_to_collide > answer[j]:
                    stack.pop()
                    continue
                
                answer[i] = time_to_collide
                break
            
            stack.append(i)
        
        return answer

The code initializes answer and a stack to maintain potential collision indices. We iterate backward, calculate collision times with the next car/fleet, and update answer accordingly. Cars that cannot be collided with are removed from the stack.

Go Solution

func getCollisionTimes(cars [][]int) []float64 {
    n := len(cars)
    answer := make([]float64, n)
    for i := range answer {
        answer[i] = -1.0
    }
    stack := []int{}
    
    for i := n - 1; i >= 0; i-- {
        positionI, speedI := cars[i][0], cars[i][1]
        
        for len(stack) > 0 {
            j := stack[len(stack)-1]
            positionJ, speedJ := cars[j][0], cars[j][1]
            
            if speedI <= speedJ {
                stack = stack[:len(stack)-1]
                continue
            }
            
            timeToCollide := float64(positionJ-positionI) / float64(speedI-speedJ)
            
            if answer[j] != -1 && timeToCollide > answer[j] {
                stack = stack[:len(stack)-1]
                continue
            }
            
            answer[i] = timeToCollide
            break
        }
        
        stack = append(stack, i)
    }
    
    return answer
}

In Go, slices are used instead of lists. Type casting to float64 ensures correct division. The logic otherwise mirrors the Python solution.

Worked Examples

Example 1: cars = [[1,2],[2,1],[4,3],[7,2]]

Iteration from right:

i	Stack	Collision Time Calculation	answer
3	[]	No car ahead	[-1,-1,-1,-1]
2	[3]	(7-4)/(3-2)=3	[-1,-1,3,-1]
1	[2,3]	Speed 1 <= 3 → pop 2; Speed 1 <= 2 → pop 3 → no collision	[-1,-1,3,-1]
0	[1]	(2-1)/(2-1)=1	[1,-1,3,-1]

Example 2: cars = [[3,4],[5,4],[6,3],[9,1]]

i	Stack	Collision Time	answer
3	[]	-1	[-1,-1,-1,-1]
2	[3]	(9-6)/(3-1)=1.5	[-1,-1,1.5,-1]
1	[2,3]	(6-5)/(4-3)=1	[-1,1,1.5,-1]
0	[1,2,3]	(5-3)/(4-4) invalid → skip, next j=2 (6-3)/(4-3)=3 > answer[2]=1.5 → skip → j=3 (9-3)/(4-1)=2 → valid	[2,1,1.5,-1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each car is pushed and popped from the stack at most once, giving linear time.
Space	O(n)	The stack and answer array each take O(n) space.

The monotonic stack ensures we only consider necessary cars for collision calculation, avoiding O(n²) brute-force comparisons.

Test Cases

# Provided examples
assert Solution().getCollisionTimes([[1,2],[2,1],[4,3],[7,2]]) == [1.0,-1.0,3.0,-1.0]  # collision with next
assert Solution().getCollisionTimes([[3,4],[5,4],[6,3],[9,1]]) == [2.0,1.0,1.5,-1.0]  # mixed collisions

# Edge cases
assert Solution().getCollisionTimes([[0,1]]) == [-1.0]  # single car
assert Solution().getCollisionTimes([[0,2],[1,2]]) == [-1.0, -1.0]  # same speed, no collision
assert Solution().getCollisionTimes([[0,5],[1,2]]) == [0.25, -1.0]  # immediate collision
assert Solution().getCollisionTimes([[0,1],[1,2],[2,3],[3,4]]) == [-1.0, -1.0, -1.0, -