D
DevExCode

LeetCode 1776: Car Fleet II Solution

Master LeetCode problem 1776 (Car Fleet II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1776 (Car Fleet II)?

This page provides optimized solutions for LeetCode problem 1776 (Car Fleet II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1776 (Car Fleet II)?

The time complexity for LeetCode 1776 (Car Fleet II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1776 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1776 in Java, C++, or Python.

Back to LeetCode Solutions