Leetcode: 1776. Car Fleet II

Mistake: Did not play with small examples draw invariants.
Can we derive an invariant based on the smallest possible examples? If there is only one car, the answer is -1. Be \(a\) and \(b\) two cars where \(b\) comes after \(a\) in the input. If \(b\) is faster than \(a\), both will have answer -1. Otherwise, \(a\) will collide with \(b\). Be \(c\) other car that come after \(b\). If \(a\) is faster than \(b\) and \(c\), then \(a\) will collide with \(c\) iff it doesn't collide first with \(b\). Therefore, we can discard all cars that go faster than \(a\) or collide with a slower car before it would collide with \(a\). These property can be implemented using a Monotonic Stack. Time and space complexity is \(O(n)\).

from typing import List


class Solution:
    def getCollisionTimes(self, c: List[List[int]]) -> List[float]:
        def t(a, b):
            return (b[0] - a[0]) / (a[1] - b[1])

        N = len(c)
        ans = [-1] * N
        st = []
        for i in range(N - 1, -1, -1):
            while st and (
                st[-1][1] >= c[i][1] or 0 < ans[st[-1][2]] <= t(c[i], st[-1])
            ):
                st.pop()
            if st:
                ans[i] = t(c[i], st[-1])
            st.append((*c[i], i))
        return ans


assert Solution().getCollisionTimes([[1, 2], [2, 1], [4, 3], [7, 2]]) == [
    1.00000,
    -1.00000,
    3.00000,
    -1.00000,
]
assert Solution().getCollisionTimes([[3, 4], [5, 4], [6, 3], [9, 1]]) == [
    2.00000,
    1.00000,
    1.50000,
    -1.00000,
]