The Car Fleet II problem involves a set of cars traveling along a one-lane road in the same direction. Each car has a unique position and speed. The cars are given as a list of cars, where each element is a pair [position, speed]. The cars are sorted in order of their positions from the frontmost to the rearmost (i.e., cars[0] is the car furthest ahead).
When a car catches up to another car ahead of it, it will form a "fleet" with the car in front, and they will travel together at the slower car's speed. Once cars have formed a fleet, they will move as a single unit, and no car in a fleet can pass another car in the same fleet.
The goal is to compute, for each car, the time it will take to catch up to the next car ahead of it (if ever). If a car never catches up to a car ahead, its fleet time is -1. The result should be an array answer where answer[i] is the time it takes for the ith car to catch up to the next car ahead.
Constraints:
-1 for cars that never catch up to the car ahead.At first glance, a brute-force approach might involve, for each car, simulating its movement forward in time to see when (if ever) it catches up to the next car ahead. However, this would be inefficient, especially as the number of cars grows.
Instead, we need to realize that only the car directly ahead matters for each car. If a car ahead forms a fleet with another car before being caught by the current car, then the current car must catch this fleet rather than the original single car. This introduces a dependency chain: the time it takes for a car to catch the fleet ahead depends on if/when the cars ahead merge into fleets.
To solve this efficiently, we can process the cars from the back (rightmost) to the front (leftmost), using a stack to keep track of the "active" fleets ahead. For each car, we determine if and when it will catch up to the nearest fleet ahead; if it does, we record the time, otherwise we record -1.
This approach avoids redundant calculations and leverages the properties of the problem to optimize the solution.
answer initialized to -1 for all cars.t = (pos_ahead - pos_current) / (speed_current - speed_ahead).answer array and push its index and time onto the stack as a new fleet.time = -1.answer array.This approach ensures that each car is processed efficiently, and the stack allows us to keep track of the evolving state of the fleets ahead.
Let's consider the following input:
cars = [[1,2],[2,1],[4,3],[7,2]]
Final answer: [1.0, -1.0, 3.0, -1.0]
The stack-based approach is much more efficient and scalable for large inputs.
The Car Fleet II problem is elegantly solved using a stack to track active fleets and their merge times. By processing cars from back to front, we efficiently determine when each car will catch up to the next fleet ahead. The key insight is that only the nearest fleet ahead matters for each car, and the stack allows us to manage the evolving state of the fleets. This results in a clean, O(n) time solution.
class Solution:
def getCollisionTimes(self, cars):
n = len(cars)
answer = [-1.0] * n
stack = [] # stack of (index, time when this fleet is caught)
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 current car is slower or same speed, it never catches up
if speed_i <= speed_j:
stack.pop()
continue
# Time to catch up
t = (pos_j - pos_i) / (speed_i - speed_j)
# If car ahead never gets caught, or we catch before it merges
if answer[j] == -1 or t <= answer[j]:
answer[i] = t
break
else:
stack.pop()
stack.append(i)
return answer
class Solution {
public:
vector<double> getCollisionTimes(vector<vector<int>>& cars) {
int n = cars.size();
vector<double> answer(n, -1.0);
stack<int> st;
for (int i = n - 1; i >= 0; --i) {
int pos_i = cars[i][0], speed_i = cars[i][1];
while (!st.empty()) {
int j = st.top();
int pos_j = cars[j][0], speed_j = cars[j][1];
if (speed_i <= speed_j) {
st.pop();
continue;
}
double t = (double)(pos_j - pos_i) / (speed_i - speed_j);
if (answer[j] == -1 || t <= answer[j]) {
answer[i] = t;
break;
} else {
st.pop();
}
}
st.push(i);
}
return answer;
}
};
class Solution {
public double[] getCollisionTimes(int[][] cars) {
int n = cars.length;
double[] answer = new double[n];
Arrays.fill(answer, -1.0);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = n - 1; i >= 0; --i) {
int pos_i = cars[i][0], speed_i = cars[i][1];
while (!stack.isEmpty()) {
int j = stack.peek();
int pos_j = cars[j][0], speed_j = cars[j][1];
if (speed_i <= speed_j) {
stack.pop();
continue;
}
double t = (double)(pos_j - pos_i) / (speed_i - speed_j);
if (answer[j] == -1 || t <= answer[j]) {
answer[i] = t;
break;
} else {
stack.pop();
}
}
stack.push(i);
}
return answer;
}
}
var getCollisionTimes = function(cars) {
const n = cars.length;
const answer = Array(n).fill(-1);
const stack = [];
for (let i = n - 1; i >= 0; --i) {
const [pos_i, speed_i] = cars[i];
while (stack.length > 0) {
const j = stack[stack.length - 1];
const [pos_j, speed_j] = cars[j];
if (speed_i <= speed_j) {
stack.pop();
continue;
}
const t = (pos_j - pos_i) / (speed_i - speed_j);
if (answer[j] === -1 || t <= answer[j]) {
answer[i] = t;
break;
} else {
stack.pop();
}
}
stack.push(i);
}
return answer;
};