Skip to content

789. Escape The Ghosts 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
 public:
  bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
    const int d = abs(target[0]) + abs(target[1]);

    for (const vector<int>& ghost : ghosts)
      if (d >= abs(ghost[0] - target[0]) + abs(ghost[1] - target[1]))
        return false;

    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
  public boolean escapeGhosts(int[][] ghosts, int[] target) {
    final int d = Math.abs(target[0]) + Math.abs(target[1]);

    for (int[] ghost : ghosts)
      if (d >= Math.abs(ghost[0] - target[0]) + Math.abs(ghost[1] - target[1]))
        return false;

    return true;
  }
}

1
2
3
4
5
6
class Solution:
  def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
    ghostSteps = min(abs(x - target[0]) +
                     abs(y - target[1]) for x, y in ghosts)

    return abs(target[0]) + abs(target[1]) < ghostSteps