Escape The Ghosts

Medium

Asked by:

33 views

Topics:

ArraysGreedy Algorithms

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.

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
-10⁴ <= x_i, y_i <= 10⁴
There can be multiple ghosts in the same location.
target.length == 2
-10⁴ <= x_target, y_target <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum values for the coordinates of the ghosts and the target, and the grid size? Should I assume they are integers?
Can the ghosts' and target's starting positions be the same?
If it's impossible to escape (i.e., a ghost can always reach me first or at the same time), what should I return?
Are the coordinates guaranteed to be within the bounds of the grid, or do I need to handle out-of-bounds situations?
If a ghost and the player reach the target simultaneously, is that considered a successful escape or a capture?

Brute Force Solution

Approach

The brute force approach to escaping ghosts means trying every single possible path you could take to get away. We calculate the distance to each ghost from every potential location we could be and see if it's safe to move there.

Here's how the algorithm would work step-by-step:

Consider every possible spot you could move to on the grid.
For each of those spots, calculate how far away you are from each ghost.
Also, for each of those spots, calculate how far the closest ghost is from its starting location to the target spot. This is the fastest that ghost can reach the destination.
Compare your distance to each ghost with how quickly the ghost can reach the spot you're considering.
If at least one ghost can reach a spot as fast as or faster than you, that spot is not safe.
Check all possible spots to determine whether there is any safe spot to move. You need to escape the ghosts before they catch you.
If after checking all spots there is no possible safe spot to move to, then it is not possible to escape the ghosts.

Code Implementation

def escape_the_ghosts(ghosts, player_start, target):    maximum_x = 20000
    maximum_y = 20000

    # Iterate through all possible spots on the grid.
    for possible_x in range(-maximum_x, maximum_x + 1):
        for possible_y in range(-maximum_x, maximum_x + 1):
            possible_position = [possible_x, possible_y]
            player_distance_to_position = manhattan_distance(player_start, possible_position)
            
            safe_spot = True
            
            # Check if any ghost can reach the position faster than the player.
            for ghost_position in ghosts:
                ghost_distance_to_target = manhattan_distance(ghost_position, target)
                ghost_distance_to_position = manhattan_distance(ghost_position, possible_position)

                # If the ghost can reach the possible location faster, its not safe.
                if ghost_distance_to_position <= player_distance_to_position:
                    safe_spot = False
                    break

            # Check if it is a safe spot and player can reach target before ghosts
            if safe_spot and manhattan_distance(player_start, target) > 0:
                return True

    return False

def manhattan_distance(point_a, point_b):
    return abs(point_a[0] - point_b[0]) + abs(point_a[1] - point_b[1])

Big(O) Analysis

Time Complexity

O(m*n*g) – Let m be the number of reachable spots on the grid (worst-case, m could be proportional to the grid size, say width*height if width and height are equal to n then m = n*n), n be the Manhattan distance between start and target, and g be the number of ghosts. For each reachable spot, we calculate the Manhattan distance to each of the g ghosts. Then for each of those ghost locations, we calculate the Manhattan distance for the ghosts to get to the target. We compare those two distances. In the worst case, we have to consider m potential target spots for the player and calculate the distance to each of the g ghosts for each of those spots. Therefore, the overall time complexity is O(m*n*g).

Space Complexity

O(1) – The provided brute force approach, when analyzed based solely on the given plain English description, calculates distances and checks for safety without explicitly creating large auxiliary data structures. The algorithm iterates through possible spots and ghosts, but the plain English explanation doesn't indicate the creation of arrays, hashmaps, or other structures to store intermediate results, visited locations, or paths. Only a few variables are needed to store distances and comparison results during the distance calculations and safety checks. Therefore, the extra space used is constant, independent of the grid size or number of ghosts.

Optimal Solution

Approach

The goal is to determine if you can escape from ghosts in a grid. The optimal strategy involves realizing you only need to compare distances rather than simulate movements. If you can reach the target faster than any ghost, you escape!

Here's how the algorithm would work step-by-step:

Figure out how far you are from the target location.
For each ghost, figure out how far *it* is from the target location.
If *any* ghost is closer to the target than you are, you cannot escape.
If you are closer to the target than *all* the ghosts, you can escape.

Code Implementation

def escape_the_ghosts(ghosts, player_location, target): 
    player_distance_to_target = abs(player_location[0] - target[0]) + abs(player_location[1] - target[1])

    # Calculate the manhattan distance for each ghost.
    for ghost_location in ghosts:
        ghost_distance_to_target = abs(ghost_location[0] - target[0]) + abs(ghost_location[1] - target[1])

        # If any ghost is closer, player can't escape.
        if ghost_distance_to_target <= player_distance_to_target:
            return False

    # Player can escape if they are closer than all ghosts.
    return True

Big(O) Analysis

Time Complexity

O(g) – The algorithm calculates the Manhattan distance between the player and the target, which takes constant time. Then, it iterates through the list of ghosts, where g represents the number of ghosts. For each ghost, it calculates the Manhattan distance to the target, also taking constant time. The time complexity is therefore directly proportional to the number of ghosts. Thus, the overall time complexity is O(g).

Space Complexity

O(1) – The space complexity is O(1) because the algorithm uses a fixed number of variables to store distances. It calculates the distance from the player to the target, and then iterates through the ghosts, calculating their distances to the target. No additional data structures that scale with the number of ghosts (N) or the grid size are created; only constant extra space is used.

Edge Cases

Case	How to Handle
Player starts at the same location as a ghost	Check if the player and a ghost have the same starting coordinates and return false immediately.
Ghosts cannot reach the target at all (obstacles prevent this)	The ghost's shortest distance will be infinite, so return true.
Player's target destination is the same as their starting position.	Check if the target position is the same as the start position and if no ghosts start at the position, return true, otherwise false.
Extremely large coordinate values for player and ghosts.	Ensure that the Manhattan distance calculation doesn't result in integer overflow.
A large number of ghosts are very close to the player's start position.	The solution should efficiently compute distances for all ghosts, and return false if at least one ghost can reach the target faster or at same time.
One or more ghosts have the exact same starting position as each other	The distance calculations won't be affected as the ghosts are treated individually.
Null or empty array of ghosts	Return true, as there are no ghosts to catch the player.
Negative coordinate values.	The Manhattan distance calculation should handle negative values correctly by using absolute values.

Player starts at the same location as a ghost

How to Handle:

Check if the player and a ghost have the same starting coordinates and return false immediately.

Ghosts cannot reach the target at all (obstacles prevent this)

How to Handle:

The ghost's shortest distance will be infinite, so return true.

Player's target destination is the same as their starting position.

How to Handle:

Check if the target position is the same as the start position and if no ghosts start at the position, return true, otherwise false.

Extremely large coordinate values for player and ghosts.

How to Handle:

Ensure that the Manhattan distance calculation doesn't result in integer overflow.

A large number of ghosts are very close to the player's start position.

How to Handle:

The solution should efficiently compute distances for all ghosts, and return false if at least one ghost can reach the target faster or at same time.

One or more ghosts have the exact same starting position as each other

How to Handle:

The distance calculations won't be affected as the ghosts are treated individually.

Null or empty array of ghosts

How to Handle:

Return true, as there are no ghosts to catch the player.

Negative coordinate values.

How to Handle:

The Manhattan distance calculation should handle negative values correctly by using absolute values.