1776. Car Fleet II
Explanation
To solve this problem, we can simulate the car movements and collisions. For each car, we calculate the time it takes to collide with the next car. If a collision occurs, we update the speed of the current car to be the speed of the slower car in the collision. We continue this process until no more collisions can occur.
We can use a stack to keep track of the cars that have not collided yet. We iterate over the cars from the back (closest to the end of the road) towards the front. For each car, we calculate the time it takes to collide with the next car. If a collision occurs, we update the speed of the current car and pop the next car from the stack. If no collision occurs, we push the current car onto the stack.
At the end of the simulation, the stack will contain the remaining cars that did not collide with the next car. We iterate over the stack to calculate the collision times for these cars.
The time complexity of this approach is O(n) where n is the number of cars.
class Solution {
public double[] getCollisionTimes(int[][] cars) {
int n = cars.length;
double[] ans = new double[n];
Stack<Integer> stack = new Stack<>();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty()) {
int j = stack.peek();
double time = (double)(cars[j][0] - cars[i][0]) / (double)(cars[i][1] - cars[j][1]);
if (time <= 0 || time >= ans[j] && ans[j] > 0) {
stack.pop();
} else {
break;
}
}
if (stack.isEmpty()) {
ans[i] = -1.0;
} else {
int j = stack.peek();
ans[i] = (double)(cars[j][0] - cars[i][0]) / (double)(cars[i][1] - cars[j][1]);
}
stack.push(i);
}
return ans;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.