Problem statement

https://leetcode.com/problems/escape-the-ghosts/

Solution

Sufficient and necessary condition is that we need to reach target before any ghost can do it: indeed if he can do it, he will do it and we can not win. If they can not reach it, it means, that there is no ghosts in circle with center in target and passing through origin. It means that if we move to our target, ghosts can not reach us.

Complexity

Time complexity is O(n), space is O(1), where n is number of ghosts.

Code

class Solution:
    def escapeGhosts(self, ghosts, T):
        D = abs(T[0]) + abs(T[1])
        return min(abs(T[0] - x) + abs(T[1]- y) for x,y in ghosts) > D