Problem

You are playing a simplified PAC-MAN game on an infinite 2-D grid. You start at the point [0, 0], and you are given a destination point target = [xtarget, ytarget] that you are trying to get to. There are several ghosts on the map with their starting positions given as a 2D array ghosts, where ghosts[i] = [xi, yi] represents the starting position of the ith ghost. All inputs are integral coordinates.

Each turn, you and all the ghosts may independently choose to either move 1 unit in any of the four cardinal directions: north, east, south, or west, or stay still. All actions happen simultaneously.

You escape if and only if you can reach the target before any ghost reaches you. If you reach any square (including the target) at the same time as a ghost, it does not count as an escape.

Return true if it is possible to escape regardless of how the ghosts move, otherwise returnfalse .

Examples

Example 1

1
2
3

Input: ghosts = [[1,0],[0,3]], target = [0,1]
Output: true
Explanation: You can reach the destination (0, 1) after 1 turn, while the ghosts located at (1, 0) and (0, 3) cannot catch up with you.

Example 2

1
2
3

Input: ghosts = [[1,0]], target = [2,0]
Output: false
Explanation: You need to reach the destination (2, 0), but the ghost at (1, 0) lies between you and the destination.

Example 3

1
2
3

Input: ghosts = [[2,0]], target = [1,0]
Output: false
Explanation: The ghost can reach the target at the same time as you.

Constraints

  • 1 <= ghosts.length <= 100
  • ghosts[i].length == 2
  • -10^4 <= xi, yi <= 10^4
  • There can be multiple ghosts in the same location.
  • target.length == 2
  • -10^4 <= xtarget, ytarget <= 10^4

Solution

Method 1 – Manhattan Distance Comparison

Intuition

You can only escape if you can reach the target strictly before any ghost. Since all can move in any direction at the same speed, the minimum number of moves to the target is the Manhattan distance. If any ghost can reach the target in the same or fewer moves than you, escape is impossible.

Approach

  1. Compute your Manhattan distance from [0,0] to target.
  2. For each ghost, compute its Manhattan distance to target.
  3. If any ghost’s distance is less than or equal to yours, return False.
  4. Otherwise, return True.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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 ghostDist = abs(g[0] - target[0]) + abs(g[1] - target[1]);
            if (ghostDist <= myDist) return false;
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int myDist = Math.abs(target[0]) + Math.abs(target[1]);
        for (int[] g : ghosts) {
            int ghostDist = Math.abs(g[0] - target[0]) + Math.abs(g[1] - target[1]);
            if (ghostDist <= myDist) return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def escapeGhosts(self, ghosts: list[list[int]], target: list[int]) -> bool:
        my_dist = abs(target[0]) + abs(target[1])
        for g in ghosts:
            ghost_dist = abs(g[0] - target[0]) + abs(g[1] - target[1])
            if ghost_dist <= my_dist:
                return False
        return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn escape_ghosts(ghosts: Vec<Vec<i32>>, target: Vec<i32>) -> bool {
        let my_dist = target[0].abs() + target[1].abs();
        for g in ghosts {
            let ghost_dist = (g[0] - target[0]).abs() + (g[1] - target[1]).abs();
            if ghost_dist <= my_dist {
                return false;
            }
        }
        true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

Complexity

  • ⏰ Time complexity: O(n), where n is the number of ghosts.
  • 🧺 Space complexity: O(1).