Introduction

In this blog post, we will explore how to solve the LeetCode problem "789" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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

Explanation

• Calculate the Manhattan distance from the starting point [0, 0] to the target. This represents the number of steps required for you to reach the target.
  • For each ghost, calculate the Manhattan distance from the ghost's starting position to the target.
  • If any ghost can reach the target in fewer steps than you, then you cannot escape. Otherwise, you can.

• Runtime Complexity: O(n), where n is the number of ghosts. Storage Complexity: O(1).

Code

    def escapeGhosts(ghosts, target):
    """
    Determines if it is possible to escape the ghosts and reach the target.

    Args:
        ghosts: A list of ghost positions (list of lists).
        target: The target position (list of integers).

    Returns:
        True if it is possible to escape, False otherwise.
    """

    my_distance = abs(target[0]) + abs(target[1])

    for ghost in ghosts:
        ghost_distance = abs(ghost[0] - target[0]) + abs(ghost[1] - target[1])
        if ghost_distance <= my_distance:
            return False

    return True