Car Fleet II: Monotone Stack Collision Times

You are given n cars on a one-lane road. Each car i has a position cars[i][0] and a speed cars[i][1]. A faster car will eventually catch a slower car ahead of it and form a fleet, traveling at the slower car's speed from that point on. Return an array answer where answer[i] is the time it takes for car i to collide with the next car ahead of it, or -1 if it never collides.

This is LeetCode 1776: Car Fleet II, a hard problem that combines monotone stack reasoning with physics-style collision math. It is a natural follow-up to the original Car Fleet problem, but the collision logic is significantly more involved because fleets cascade: when car A catches car B, car B might have already caught car C and slowed down.

Why this problem matters

Car Fleet II teaches you to think about "future state" when processing a stack. In simpler monotone stack problems like Daily Temperatures, you just compare values directly. Here, you have to reason about what happens after a collision occurs. A car on the stack might get absorbed into a fleet at some future time, and you need to account for that when calculating whether a car behind it can catch up before that absorption happens.

This kind of reasoning, where stack elements have lifetimes that affect your decisions, shows up in scheduling problems, event simulation, and any scenario where entities expire or change state over time.

The key insight

Process cars from right to left. Maintain a stack of cars that are still "alive" (not yet absorbed by a fleet ahead of them). For each new car, check if it can catch the car on top of the stack:

1. If the current car is not faster than the stack top car, it will never catch it. Pop and try the next car on the stack.
2. If the current car is faster, calculate the collision time. But there is a catch: if the stack top car itself gets absorbed into a fleet before the current car reaches it, then the collision is invalid. Pop the stack top and try again.
3. When you find a valid collision (or the stack is empty), record the answer and push the current car.

The critical check is: if collisionTime is greater than the stack top's own collision time (and the stack top's collision time is not -1), the stack top car will have already been absorbed. You need to skip past it and check the next car on the stack.

The solution

def get_collision_times(cars: list[list[int]]) -> list[float]:
    n = len(cars)
    answer = [-1.0] * n
    stack = []

    for i in range(n - 1, -1, -1):
        pos_i, speed_i = cars[i]

        while stack:
            j = stack[-1]
            pos_j, speed_j = cars[j]

            if speed_i <= speed_j:
                stack.pop()
                continue

            collision_time = (pos_j - pos_i) / (speed_i - speed_j)

            if answer[j] == -1 or collision_time <= answer[j]:
                answer[i] = collision_time
                break

            stack.pop()

        stack.append(i)

    return answer

Let's walk through what each piece does.

The outer loop iterates from the rightmost car to the leftmost. This is the standard direction for monotone stack problems where you need to look "ahead" (to the right).

Inside the while loop, we examine the car at the top of the stack. If the current car's speed is not greater than the stack top's speed, the current car can never catch it, so we pop it. A slower or equal-speed car ahead is irrelevant because we will never reach it.

When the current car is faster, we compute the collision time using the basic formula: distance divided by relative speed. But we then check whether the stack top car will still be around at that time. If answer[j] is not -1 and our collision time exceeds answer[j], the stack top car will have already merged into a fleet and slowed down. That makes our calculation invalid, so we pop and try the next car.

When we find a valid collision or exhaust the stack, we record the answer and push the current car's index.

Visual walkthrough

Let's trace through the example cars = [[1,2], [4,4], [7,1], [11,3]] step by step. We process from right to left and build the answer array as we go.

Notice how car 1 gets popped from the stack when processing car 0. Even though car 1 is ahead of car 0, car 1 will collide with car 2 at t=1.0 and slow down to speed 1. Car 0 (speed 2) would need to catch car 1 at its original speed 4, which is impossible since car 0 is slower. So car 1 is irrelevant, and we look past it to car 2 instead.

Complexity analysis

Time is O(n). Each car is pushed onto the stack exactly once and popped at most once. Even though there is a while loop inside the for loop, the total number of pop operations across all iterations cannot exceed n. This is the standard amortized analysis for monotone stack algorithms.

Space is O(n) for the stack and the answer array. In the worst case (all cars are in decreasing speed order), every car stays on the stack.

The building blocks

1. Right-to-left monotone stack traversal

stack = []
for i in range(n - 1, -1, -1):
    while stack and should_pop(i, stack[-1]):
        stack.pop()
    process(i, stack)
    stack.append(i)

This is the skeleton for any problem where you need to find the "next relevant element" to the right. You process from right to left, maintain a stack of candidates, and pop elements that become irrelevant. The same pattern powers Daily Temperatures, Next Greater Element, and Largest Rectangle in Histogram.

2. Collision time with validity check

collision_time = (pos_j - pos_i) / (speed_i - speed_j)

if answer[j] == -1 or collision_time <= answer[j]:
    answer[i] = collision_time
    break

This is the unique part of Car Fleet II. After computing a collision time, you validate it against the stack top's own collision time. If the stack top gets absorbed first, the collision is impossible and you need to look further. This validity check is what separates a simple monotone stack from one that reasons about "future state."

Edge cases

• All cars have the same speed: no car ever catches another. Every answer is -1.
• Cars are already sorted by decreasing speed: each car catches the one ahead of it. The stack never needs to pop.
• Two cars at very close positions with a tiny speed difference: the collision time can be extremely large. Make sure you use floating-point division, not integer division.
• Only one car: return [-1] since there is nothing to collide with.
• A chain of collisions: car A catches B, B catches C, C catches D. The stack pops multiple elements when processing A, but each pop is amortized O(1).

From understanding to recall

The Car Fleet II pattern has two layers: the standard right-to-left monotone stack traversal and the collision validity check. Understanding both layers conceptually is one thing. Writing them correctly under pressure, remembering to check answer[j] against collision_time and getting the pop condition right, is another.

Spaced repetition bridges that gap. You practice the right-to-left stack skeleton, the collision time formula, and the validity check as separate building blocks. After a few rounds of active recall, you stop second-guessing the details. The pattern flows naturally and you can focus on the problem-specific reasoning instead of fighting the boilerplate.

Related posts

• Daily Temperatures - another monotone stack problem tracking when elements meet conditions
• Largest Rectangle in Histogram - monotone stack for finding boundaries
• Car Fleet - the predecessor problem with simpler fleet formation logic

CodeBricks breaks Car Fleet II into its right-to-left stack traversal and collision validity building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a hard stack problem shows up in your interview, you do not hesitate. You just write it.