Car Fleet II

Car Fleet II

What is this problem about?

The Car Fleet II interview question is a much more complex version of the original. Instead of counting fleets at a target, you need to find the exact time each car will collide with the car in front of it. If a car never collides, the time is -1. This Car Fleet II coding problem involves dynamic collisions where a car might collide with a fleet that was already formed by two other cars.

Why is this asked in interviews?

Google uses this HARD-level problem to test a candidate's ability to use Monotonic Stacks for complex interval/event processing. It requires calculating not just if a collision happens, but when it happens, and whether that collision occurs before or after the target car has already merged into another fleet. It’s a test of high-level mathematical and algorithmic reasoning.

Algorithmic pattern used

This uses the Array, Math, Monotonic Stack, Stack interview pattern.

• Process cars from right to left (the lead car first).
• Maintain a stack of cars that could potentially be collided with.
• For the current car, check the car on top of the stack. A collision is possible if the current car is faster.
• If a collision is possible, calculate the time. If this time is greater than the collision time of the car on the stack, the current car will actually hit the fleet after the car on the stack has already merged. In this case, pop the stack and try the next car.

Example explanation

Car 1 (lead): Speed 2. Car 2 (behind): Speed 4. Car 3 (furthest back): Speed 5.

1. Car 1: -1 (nothing in front).
2. Car 2: Faster than Car 1. Collides at T1.
3. Car 3: Faster than Car 2. Calculate collision time T2 with Car 2.
4. If T2 < T1, Car 3 hits Car 2 first. If T2 > T1, Car 3 actually hits the Car 1/Car 2 fleet.

Common mistakes candidates make

• Simulating over time: Trying to move cars in small increments, which is extremely inefficient (O(T * N)).
• Complexity: Not using a monotonic stack, leading to O(N^2) checks for every car pair.
• Popping incorrectly: Failing to realize that once a car merges into a fleet, it effectively takes on the properties of that fleet's leader for any cars behind it.

Interview preparation tip

Practice "Right-to-Left Monotonic Stack" problems. This is a common pattern for "what happens to me based on the people in front of me" scenarios.