We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Escape The Ghosts

Number: 805

Difficulty: Medium

Paid? No

Companies: Wix, Google

Problem Description

You start at point [0, 0] and try to reach a target point on an infinite 2-D grid. Several ghosts, each starting at a given position, can move one step (or stay) simultaneously with you. You escape if you can reach the target before any ghost can reach you (or the target). If a ghost and you arrive at the same time, you do not escape.

Key Insights

  • The movement is based on Manhattan distance since moves are in the four cardinal directions.
  • The solution hinges on comparing the Manhattan distance from the starting position to the target with each ghost's Manhattan distance to the target.
  • If any ghost can reach the target with a distance that is less than or equal to your distance, then escape is impossible.

Space and Time Complexity

Time Complexity: O(n) where n is the number of ghosts (we iterate through all ghosts once).
Space Complexity: O(1) since only a few variables are used.

Solution

The main idea is to calculate your minimum number of steps to the target (Manhattan distance from [0, 0] to target). Then, for each ghost, compute its Manhattan distance to the target. If any ghost's distance is less than or equal to yours, it means that ghost can intercept or reach the target as fast as or faster than you can, making your escape impossible. We therefore return false in that case; otherwise, return true. Data structures used include simple integer variables and arrays/lists for holding ghost positions. The algorithm is a straightforward iteration over the ghost list with constant-time calculations (Manhattan distance calculation).

Code Solutions

# Define the function to check if escape is possible
def escapeGhosts(ghosts, target):
    # Calculate the Manhattan distance from start (0,0) to target
    my_distance = abs(target[0]) + abs(target[1])
    
    # Iterate over each ghost's starting position
    for ghost in ghosts:
        # Calculate the Manhattan distance from the ghost to the target
        ghost_distance = abs(ghost[0] - target[0]) + abs(ghost[1] - target[1])
        # Check if ghost can reach target before or at the same time as you
        if ghost_distance <= my_distance:
            return False
    # If no ghost can intercept, you can escape
    return True

# Example usage:
print(escapeGhosts([[1,0],[0,3]], [0,1]))  # Expected output: True
← Back to All Questions