Escape The Ghosts

Problem Description

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 = [x_target, y_target] 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] = [x_i, y_i] represents the starting position of the i-th 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.

Key Insights

• The distance you need to cover to reach the target is the Manhattan distance from [0, 0] to [x_target, y_target].
• Each ghost can also reach the target based on their respective positions.
• You need to ensure your time to the target is less than any ghost's time to the target.
• If any ghost can reach the target at the same time or sooner than you, you cannot escape.

Space and Time Complexity

Time Complexity: O(n) where n is the number of ghosts, as we need to check the distance for each ghost. Space Complexity: O(1) since we are using a fixed number of variables for calculations.

Solution

To solve the problem, we will:

1. Calculate your Manhattan distance to the target from the starting point [0, 0].
2. For each ghost, calculate its Manhattan distance to the target.
3. Compare your distance to each ghost's distance. If your distance is less than all ghosts' distances, return true. If any ghost can reach the target at the same time or sooner, return false.

Code Solutions