Escape The Ghosts

medium math geometry manhattan-distance

Problem

You start at (0,0) and want to reach target. Ghosts start at given positions. Each turn everyone moves one step in any cardinal direction. Determine if you can reach target before any ghost catches you.

Inputghosts = [[1,0],[0,3]], target = [0,1]

Outputtrue

You reach target in 1 step; nearest ghost needs 2 steps.

ghosts, target

def escapeGhosts(ghosts, target):
    my_dist = abs(target[0]) + abs(target[1])
    for g in ghosts:
        gd = abs(g[0] - target[0]) + abs(g[1] - target[1])
        if gd <= my_dist:
            return False
    return True

var escapeGhosts = function(ghosts, target) {
    const myDist = Math.abs(target[0]) + Math.abs(target[1]);
    for (const g of ghosts) {
        const gd = Math.abs(g[0] - target[0]) + Math.abs(g[1] - target[1]);
        if (gd <= myDist) return false;
    }
    return true;
};

class Solution {
    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int myDist = Math.abs(target[0]) + Math.abs(target[1]);
        for (int[] g : ghosts) {
            int gd = Math.abs(g[0] - target[0]) + Math.abs(g[1] - target[1]);
            if (gd <= myDist) return false;
        }
        return true;
    }
}

class Solution {
public:
    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
        int myDist = abs(target[0]) + abs(target[1]);
        for (auto& g : ghosts) {
            int gd = abs(g[0] - target[0]) + abs(g[1] - target[1]);
            if (gd <= myDist) return false;
        }
        return true;
    }
};

Explanation

The whole problem boils down to one neat insight: you escape if and only if you can reach the target in fewer steps than every ghost. No simulation of movement is needed.

Since everyone moves one cardinal step per turn, the time to reach a point is just its Manhattan distance (the sum of horizontal and vertical gaps). Your distance from (0,0) to the target is my_dist = abs(target[0]) + abs(target[1]).

For each ghost we compute its Manhattan distance to the same target. If any ghost's distance is <= my_dist, that ghost can sit on the target (or intercept you) by the time you arrive, so we return False.

If no ghost is that close, you arrive strictly first and the function returns True. The key subtlety is comparing each ghost's distance to the target, not to you.

Example: target (0,1) so my_dist = 1. Ghost (1,0) is distance 2 away, ghost (0,3) is distance 2. Both exceed 1, so you escape: true.

Time: O(g) Space: O(1)