{x}
blog image

Escape The Ghosts

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 <= 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

Solution Explanation

This problem asks whether a player can reach a target point before any ghosts can catch them. The key insight is that we don't need to simulate movement; we can simply compare distances. The player's distance to the target is a lower bound on the time it takes to reach the target. If any ghost's distance to the target plus the ghost's distance to the starting point (0,0) is less than or equal to the player's distance to the target, then that ghost can potentially catch the player.

Algorithm:

  1. Calculate Player's Distance: Compute the Manhattan distance from (0, 0) to the target using the formula abs(tx) + abs(ty), where tx and ty are the x and y coordinates of the target.

  2. Iterate Through Ghosts: For each ghost:

    • Calculate the ghost's Manhattan distance to the target using abs(tx - x) + abs(ty - y).
    • Calculate the ghost's Manhattan distance to the starting point (0,0) using abs(x) + abs(y).
    • Check if the sum of the ghost's distance to the target and its distance to the starting point is less than or equal to the player's distance to the target. If it is, the ghost can potentially catch the player, so return false.

  3. Escape Successful: If the loop completes without finding any ghost that can catch the player, return true.

Time Complexity Analysis:

  • The algorithm iterates through each ghost once. The calculations inside the loop are constant time.
  • Therefore, the overall time complexity is O(G), where G is the number of ghosts.

Space Complexity Analysis:

  • The algorithm uses only a constant amount of extra space to store variables.
  • Therefore, the space complexity is O(1).

Code Explanation (Python):

class Solution:
    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
        tx, ty = target # unpack target coordinates for readability
        player_dist = abs(tx) + abs(ty) # player's distance to target
 
        for x, y in ghosts: # iterate through each ghost
            ghost_dist_to_target = abs(tx - x) + abs(ty - y) # ghost's distance to target
            ghost_dist_to_origin = abs(x) + abs(y) # ghost's distance to origin
            if ghost_dist_to_target + ghost_dist_to_origin <= player_dist: # check if ghost can catch player
                return False # if ghost can catch, return false
 
        return True # if no ghost can catch, return true

The code in other languages follows the same logic, only differing in syntax. The core algorithm remains consistent across all implementations, maintaining the O(G) time and O(1) space complexity.