Escape The Ghosts

In the Escape The Ghosts problem, you must determine if you can reach a target on an infinite grid before any ghost catches you. This involves calculating distances and comparing your speed with the ghosts' movements. If you can reach the target before any ghost does, you escape.

Problem Statement

In this problem, you play a simplified PAC-MAN game on an infinite 2-D grid. Starting at [0, 0], your goal is to reach the target location [xtarget, ytarget]. Multiple ghosts are positioned on the grid, each starting at a specific coordinate given by a 2D array. Your goal is to determine if you can reach the target before any ghost does.

Each turn, you and the ghosts can move one unit in any of the four cardinal directions or stay still. The goal is to escape by reaching the target before the ghosts. If you reach the target at the same time as any ghost, it is not counted as an escape.

Examples

Example 1

Input: ghosts = [[1,0],[0,3]], target = [0,1]

Output: true

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

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

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 Approach

Manhattan Distance Calculation

Use the Manhattan distance (sum of the absolute differences in the x and y coordinates) to calculate the time it would take for you and each ghost to reach the target. If your time is shorter than any ghost’s time, you escape.

Ghost vs Player Comparison

For each ghost, calculate the distance to the target. Compare each ghost's time to your own time to ensure no ghost reaches the target before you do.

Early Exit Optimization

As soon as you detect a ghost that reaches the target at the same time or faster than you, return false, as no escape is possible.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) where n is the number of ghosts, as we need to check each ghost’s position to calculate its distance to the target. The space complexity is O(1), as no additional space is used aside from a few variables for calculations.

What Interviewers Usually Probe

• Look for efficient handling of the distance calculation.
• Check the approach to early exits and minimal computation.
• Assess how the solution scales when more ghosts are added.

Common Pitfalls or Variants

Common pitfalls

• Misunderstanding the simultaneous movement of ghosts and the player.
• Incorrectly comparing distances by neglecting the Manhattan distance formula.
• Failing to optimize for early exits, potentially leading to slower solutions.

Follow-up variants

• Incorporate dynamic grid changes where some obstacles appear along the path.
• Introduce ghosts with different speeds and behavior patterns.
• Adjust the problem to allow ghosts to react differently, such as following you.

FAQ

How do I calculate the distance in Escape The Ghosts?

Use the Manhattan distance formula: $|x_1 - x_2| + |y_1 - y_2|$ to determine how long it takes for the player and ghosts to reach the target.

What happens if I reach the target at the same time as a ghost?

If you reach the target at the same time as any ghost, you do not escape, and the output should be false.

What is the time complexity of solving Escape The Ghosts?

The time complexity is O(n) where n is the number of ghosts because we calculate the distance for each ghost to the target.

What is the significance of early exit in Escape The Ghosts?

Early exit improves efficiency by stopping the computation as soon as a ghost reaches the target faster than or at the same time as the player.

How does Escape The Ghosts relate to array-based algorithms?

Escape The Ghosts involves manipulating arrays for ghost positions and using mathematical comparisons, combining array handling with distance calculations.