Watch 9 video solutions for Escape The Ghosts, a medium level problem involving Array, Math. This walkthrough by code Explainer has 1,195 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 104Problem Overview: You start at (0,0) on an infinite grid and want to reach a target coordinate. Several ghosts start at different positions and can move one step per turn in the four cardinal directions. If any ghost reaches the target at the same time or earlier than you, escape becomes impossible. The task is to determine whether you can guarantee reaching the target before any ghost intercepts.
Approach 1: Brute Force Simulation (Exponential Time, O(k) Space)
A direct idea is to simulate movement on the grid. From (0,0), explore all possible paths toward the target using BFS or DFS while simultaneously tracking ghost positions at each time step. At every move, check whether a ghost can reach the same cell at the same or earlier time. The grid is theoretically unbounded, so the search space grows rapidly and becomes impractical without heavy pruning. Time complexity becomes exponential in the path length, while space complexity is O(k) for storing frontier states and ghost positions.
This method demonstrates the problem mechanics but is rarely used in practice. It helps confirm that movement is symmetric in all directions and that timing is the key constraint.
Approach 2: Manhattan Distance Comparison (O(n) Time, O(1) Space)
The key observation is that the shortest path on a grid with four-directional movement equals the Manhattan distance. Your distance from the start to the target is |target_x| + |target_y|. Each ghost can also reach the target using its Manhattan distance |ghost_x - target_x| + |ghost_y - target_y|. If any ghost's distance to the target is less than or equal to yours, that ghost can intercept or reach the target at the same time.
Instead of simulating movement, iterate through the ghost positions stored in the array and compute their Manhattan distance using simple math operations. The moment a ghost distance <= your distance, escape is impossible. If every ghost is strictly farther away, you will always reach the target first.
This works because ghosts can always mirror your path or choose the optimal route on the grid. Therefore, distance alone determines the outcome. The algorithm scans the ghost list once, giving O(n) time complexity and constant O(1) extra space.
Recommended for interviews: The Manhattan Distance Comparison approach is what interviewers expect. It reduces a movement simulation problem into a simple mathematical observation. Showing the brute force idea first demonstrates problem understanding, but recognizing the Manhattan distance property shows strong algorithmic intuition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | Exponential | O(k) | Useful for understanding movement rules or verifying small cases |
| Manhattan Distance Comparison | O(n) | O(1) | Optimal approach for interviews and production solutions |