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.
Example 1:
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 <= 100ghosts[i].length == 2-104 <= xi, yi <= 104target.length == 2-104 <= xtarget, ytarget <= 104The key idea in Escape The Ghosts is to compare the Manhattan distance from different starting points to the target. Since everyone moves one step at a time in four directions, the minimum number of moves required to reach the target equals the Manhattan distance: |x1 - x2| + |y1 - y2|.
Start by computing the distance from the player's position (the origin) to the target. Then evaluate the distance from each ghost to the same target. If any ghost can reach the target in the same number of moves or fewer, it can intercept or arrive at the destination first, making escape impossible.
This observation eliminates the need for path simulation or BFS traversal. Instead, a simple pass through the ghost positions with basic arithmetic is enough. The approach leverages array iteration and distance comparison, making the implementation concise and efficient.
The algorithm runs in O(n) time where n is the number of ghosts, with constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Manhattan Distance Comparison | O(n) | O(1) |
Fireship
This approach calculates the Manhattan distance from the starting point (0,0) to the target for you, and for each ghost from their starting position to the target. You can only escape if your distance to the target is strictly less than every ghost's distance to the target, meaning you reach the destination before any ghost can get there.
Time Complexity: O(n), where n is the number of ghosts. Space Complexity: O(1).
1class Solution {
2 public boolean escapeGhosts(int[][] ghosts, int[] target) {
3 int playerDist = Math.abs(This Java code uses Manhattan distance calculations. It returns false if any ghost can reach the target as fast or faster than the player.
This approach involves simulating every possible move for you and each ghost simultaneously. For each time step, move each entity towards the target or keep them in the same position if they're already there. This approach is generally inefficient but illustrates the problem space.
Time Complexity: O(n), where n is the number of ghosts. Space Complexity: O(1).
1public class Solution {
public bool BruteForceEscape(int[][] ghosts, int[] target) {
int playerDist = Math.Abs(target[0]) + Math.Abs(target[1]);
foreach (int[] ghost in ghosts) {
int ghostDist = Math.Abs(ghost[0] - target[0]) + Math.Abs(ghost[1] - target[1]);
if (ghostDist <= playerDist) {
return false;
}
}
return true;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of grid distance and Manhattan distance problems frequently appear in technical interviews, including FAANG-style interviews. The problem tests mathematical insight, reasoning, and the ability to simplify seemingly complex movement scenarios.
A simple array iteration is sufficient because the problem only requires checking distances for each ghost. No advanced data structures like graphs or queues are needed. The solution mainly relies on arithmetic calculations.
The optimal approach compares the Manhattan distance from the player and each ghost to the target. If any ghost can reach the target in the same or fewer moves than the player, escape is impossible. This avoids complex pathfinding and reduces the solution to simple distance checks.
Movement on the grid is limited to four directions, meaning the shortest path equals the Manhattan distance between two points. This metric directly represents the minimum number of moves required to reach the target.
This C# function simplifies brute force by evaluating distances rather than simulating every possible move.