Problem statement

https://leetcode.com/problems/car-fleet-ii/

Solution

The idea is to use monotonic stack idea: we will always keep in our stack some cars such that we have increasing speeds, it will be our fleets, which will never gain each another. We will keep tuples of 3 numbers: (position, speed, collision time). Let us traverse cars from the end and check the following conditions: consider car X with positoin and speed (p, s).

  1. If speed s <= stack[-1][1], then it means that the speed of current car is less or equal than the last car in our stack (which is closest to X in our stack) and it means that it will never gain it. We can remove last car from stack from consideration, because all previous cars to X can not gain it.
  2. Also let us consider function gain is time when one car will catch another. If it happens that possible gain time of car X and the last car in stack is more than collision time of last car in stack, again no need to consider this car and we remove it from stack: this collition will never happen: imagine stack = [(5, 1, inf), (3, 3, 1)] and new element is (1, 4). Then we have graph like this:

image.png

So, last element from stack can be removed: it can be seen that even though red car can reach green, but it does not matter for blue car: it will just ignore it.

Finally, if stack is empty, we append (p, s, inf) in our stack, that is collision time for this car is infinite: it will never collide with anyone. If stack is not empty, we will add (p, s, time) to our stack, where time is gain time of last car in stack and car X.

Complexity

It is O(n) for time and space

Code

class Solution:
    def getCollisionTimes(self, cars):
        result, stack = [], []
        def gain(A, B):
            return (A[0] - B[0]) / (B[1] - A[1])

        for p, s in cars[::-1]:
            while stack and (s <= stack[-1][1] or gain((p, s), stack[-1]) >= stack[-1][2]):
                stack.pop()
                
            time = gain((p, s), stack[-1]) if stack else float("inf")

            stack.append((p, s, time))
            result.append(time)

        return [-1 if x == inf else x for x in result[::-1]]

Remark

Note, that in fact what we need to look in convex hull of car trajectories.