In this guide, you will get 789. Escape The Ghosts LeetCode Solution with the best time and space complexity. The solution to Escape The Ghosts problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 return false.
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:
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:
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
-104 <= xi, yi <= 104
There can be multiple ghosts in the same location.
target.length == 2
-104 <= xtarget, ytarget <= 104
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
789. Escape The Ghosts LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
789. Escape The Ghosts LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
789. Escape The Ghosts LeetCode Solution in Python
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 # code by PROGIEZ
