There are n cars traveling at different speeds in the same direction along a one-lane road. You are given an array cars of length n, where cars[i] = [positioni, speedi] represents:


	positioni is the distance between the ith car and the beginning of the road in meters. It is guaranteed that positioni &lt; positioni+1.
	speedi is the initial speed of the ith car in meters per second.


For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the slowest car in the fleet.

Return an array answer, where answer[i] is the time, in seconds, at which the ith car collides with the next car, or -1 if the car does not collide with the next car. Answers within 10-5 of the actual answers are accepted.

&nbsp;
Example 1:

Input: cars = [[1,2],[2,1],[4,3],[7,2]]
Output: [1.00000,-1.00000,3.00000,-1.00000]
Explanation: After exactly one second, the first car will collide with the second car, and form a car fleet with speed 1 m/s. After exactly 3 seconds, the third car will collide with the fourth car, and form a car fleet with speed 2 m/s.


Example 2:

Input: cars = [[3,4],[5,4],[6,3],[9,1]]
Output: [2.00000,1.00000,1.50000,-1.00000]


&nbsp;
Constraints:


	1 &lt;= cars.length &lt;= 105
	1 &lt;= positioni, speedi &lt;= 106
	positioni &lt; positioni+1


class Car:
    def __init__(self, pos, speed, idx, prev=None, next=None):
        self.pos = pos
        self.speed = speed
        self.idx = idx
        self.prev = prev
        self.next = next

class Solution:
    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
        colis_times = [-1] * len(cars)
        cars = [Car(pos, sp, i) for i, (pos, sp) in enumerate(cars)]
        for i in range(len(cars)-1): cars[i].next = cars[i+1]
        for i in range(1, len(cars)): cars[i].prev = cars[i-1]
        
        catchup_order = [((b.pos-a.pos)/(a.speed-b.speed), a.idx, a)
                        for i, (a, b) 
                        in enumerate(zip(cars, cars[1:])) if a.speed > b.speed]
        heapify(catchup_order)
        
        while catchup_order:
            catchup_time, idx, car = heappop(catchup_order)
            if colis_times[idx] > -1: continue # ith car has already caught up
            colis_times[idx] = catchup_time
            if not car.prev: continue # no car is following us
            car.prev.next, car.next.prev = car.next, car.prev
            if car.next.speed >= car.prev.speed: continue # the follower is too slow to catch up
            new_catchup_time = (car.next.pos-car.prev.pos)/(car.prev.speed-car.next.speed)
            heappush(catchup_order, (new_catchup_time, car.prev.idx, car.prev))
        
        return colis_times
class Solution {
    public double[] getCollisionTimes(int[][] cars) {
        int n = cars.length;
        double[] res = new double[n];
        Arrays.fill(res, -1.0);

        // as soon as a car c1 catches another car c2, we can say c1 vanishes into c2; meaning that
        // after catching c2, we may view c1 as non-existing (cars before c1 may not catches c1);

        /** Define a stack storing the index of cars as follows:

        Assuming cars c_0, c_1, c_2, ... , c_k are in the stack, they satisfy:
            1. v0 > v1 > v2 ... > vk where v_i is the velocity of car c_i
            2. c_(i+1) is the car that c_i vanishes into

        Namely, if only these cars exist, then what will happened is that c_0 vanishes into c_1,
        then c_1 vanishes into c_2, ..., c_(k-1) vanishes into c_k;
        */
        Deque<Integer> stack = new LinkedList<>();
        for (int i = n-1; i >= 0; i--) {
            int[] c1 = cars[i];
            while (!stack.isEmpty()) {
                int j = stack.peekLast();
                int[] c2 = cars[j];

                /** If both conditions are satisfied:
                    1. c1 is faster than c2
                    2. c1 catches c2 before c2 vanishes into other car

                Then we know that c2 is the car that c1 catches first (i.e., c1 vanishes into c2)
                    ==> get the result for c1

                Note neither c1 nor c2 is polled out from the stack considering the rule of stack.
                */

                if (c1[1] > c2[1] && (res[j] == -1.0 || catchTime(cars, i, j) <= res[j])) {
                    res[i] = catchTime(cars, i, j);
                    break;
                }

                /** Now we have either one of situations
                    1. c1 is slower than c2
                    2. c1 potentially catches c2 AFTER c2 vanishes

                    Claim: no car before c1 will vanish into c2

                    1. ==> cars before c1 will vanish into c1 first before catching c2
                    2. <==> c2 "vanishes" into another car even before c1 catches it

                Either way, c2 can not be catched by c1 or cars beofre c1 ==> poll it out from stack

                */
                stack.pollLast();
            }
            stack.offerLast(i);
        }
        return res;
    }

    // time for cars[i] to catch cars[j]
    private double catchTime(int[][] cars, int i, int j) {
        int dist = cars[j][0] - cars[i][0];
        int v = cars[i][1] - cars[j][1];

        return (double)dist / v;
    }
}
class Solution {
public:
    vector<double> getCollisionTimes(vector<vector<int>>& cars)
    {
        int n = cars.size();
        vector<double> res(n,-1.0);
        stack<int> st;// for storing indices
        for(int i=n-1;i>=0;i--)
        {
    //traversing from back if someone has greater speed and ahead of lesser speed car it will always be ahead 
            while(!st.empty() && cars[st.top()][1]>= cars[i][1])
                st.pop();
            while(!st.empty()) // for lesser speed car ahead of greater spped car
            {
                double collision_time = (double)(cars[st.top()][0]-cars[i][0])/(cars[i][1]-cars[st.top()][1]);
                if(collision_time <=res[st.top()] || res[st.top()] == -1)
                {
                    res[i] = collision_time;
                    break;
                }
                st.pop();
            }
            
            st.push(i);
        }
        return res;
    }
};
var getCollisionTimes = function(cars) {
    // create a stack to hold all the indicies of the cars that can be hit
    const possibleCarsToHit = [];
    const result = new Array(cars.length).fill(-1);
	
    for (let i = cars.length - 1; i >= 0; i--) {
	
	    // if there are cars to hit, check if the current car will hit the car before or after hitting
		// the car in front of them
		// you can also think of this as if the current car will hit the car before or after being absorbed by
		// the slower car in front.
        while (possibleCarsToHit.length && result[possibleCarsToHit[possibleCarsToHit.length - 1]] >= 0) {
            const nextCarIndex = possibleCarsToHit[possibleCarsToHit.length - 1];
            const timeToCatchNextCar = 
                getTimeToCatchNextCar(cars[i], cars[nextCarIndex]);
            const timeToCatchNextNextCar = result[nextCarIndex];
            if (timeToCatchNextCar > 0 && 
                timeToCatchNextCar <= timeToCatchNextNextCar) {
				break;
			}
			
			// pop off the stack because the car was absorbed by the next car
			// before getting hit by the current car
            possibleCarsToHit.pop();
        }
        if (possibleCarsToHit.length) {
            const nextCarIndex = possibleCarsToHit[possibleCarsToHit.length - 1];
            result[i] = getTimeToCatchNextCar(cars[i], cars[nextCarIndex]);
        }
        possibleCarsToHit.push(i);
    }
    return result;
};
    
    
function getTimeToCatchNextCar(leftCar, rightCar) {
    const [leftCarPosition, leftCarSpeed] = leftCar
    const [rightCarPosition, rightCarSpeed] = rightCar;
    const distanceToCatchCar = rightCarPosition - leftCarPosition;
    const differenceInSpeed = leftCarSpeed - rightCarSpeed;
    return differenceInSpeed > 0 ? distanceToCatchCar / differenceInSpeed : -1;
}
Car Fleet II