Code Implementation

class Solution:
    def escapeGhosts(self, ghosts, target):
        # Calculate the player's minimum distance to the target
        player_dist = abs(target[0]) + abs(target[1])
        # If any ghost can reach the target as fast or faster, return False
        for ghost in ghosts:
            ghost_dist = abs(ghost[0] - target[0]) + abs(ghost[1] - target[1])
            if ghost_dist <= player_dist:
                return False
        return True
      

class Solution {
public:
    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
        int playerDist = abs(target[0]) + abs(target[1]);
        for (const auto& ghost : ghosts) {
            int ghostDist = abs(ghost[0] - target[0]) + abs(ghost[1] - target[1]);
            if (ghostDist <= playerDist) return false;
        }
        return true;
    }
};
      

class Solution {
    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int playerDist = Math.abs(target[0]) + Math.abs(target[1]);
        for (int[] ghost : ghosts) {
            int ghostDist = Math.abs(ghost[0] - target[0]) + Math.abs(ghost[1] - target[1]);
            if (ghostDist <= playerDist) return false;
        }
        return true;
    }
}
      

var escapeGhosts = function(ghosts, target) {
    const playerDist = Math.abs(target[0]) + Math.abs(target[1]);
    for (let ghost of ghosts) {
        const ghostDist = Math.abs(ghost[0] - target[0]) + Math.abs(ghost[1] - target[1]);
        if (ghostDist <= playerDist) return false;
    }
    return true;
};
      

Problem Description

In the "Escape The Ghosts" problem, you start at the origin [0, 0] on a 2D grid. There are several ghosts, each with their own starting positions given as a list ghosts, where each ghost's position is a pair of integers. Your goal is to reach a given target position, also specified as a pair of integers.

Both you and the ghosts can move one unit per turn in any of the four cardinal directions (up, down, left, right). All move simultaneously. If a ghost reaches the target before you, or at the same time as you, you lose. If you can reach the target strictly before any ghost, you win.

Key constraints:

• You move from [0, 0] to target.
• Ghosts can move optimally to block you.
• If any ghost reaches the target at the same time or before you, you cannot escape.

Thought Process

At first glance, it may seem that you need to simulate every possible move for both you and each ghost, considering all possible paths. However, both you and the ghosts can move in any direction, and all are allowed to take the shortest possible path to the target.

The key insight is that the only thing that matters is the minimal number of steps required for you and each ghost to reach the target. Since all parties can move optimally, the actual path doesn't matter—just the distance.

This reduces the problem to a simple distance comparison: if any ghost can reach the target in the same number of steps or fewer than you, you cannot escape. Otherwise, you can always reach the target first.

Solution Approach

Let's break down the algorithm step by step:

1. Calculate Your Distance:
   • Since you start from [0, 0], your minimum number of steps to the target is the Manhattan distance: abs(target[0]) + abs(target[1]).
2. Calculate Each Ghost's Distance:
   • For each ghost, compute their Manhattan distance to the target: abs(ghost[0] - target[0]) + abs(ghost[1] - target[1]).
3. Compare Distances:
   • If any ghost's distance is less than or equal to your distance, you cannot escape (return False).
   • If all ghosts are farther away, you can escape (return True).

We use simple arithmetic and a loop to compare distances, making the solution efficient and straightforward.

Example Walkthrough

Let's consider the following example:

• ghosts = [[1, 0], [0, 3]]
• target = [0, 1]

Your distance:
From [0, 0] to [0, 1] is abs(0-0) + abs(0-1) = 1.

Ghost 1:
From [1, 0] to [0, 1] is abs(1-0) + abs(0-1) = 2.

Ghost 2:
From [0, 3] to [0, 1] is abs(0-0) + abs(3-1) = 2.

Both ghosts are 2 steps away, while you are only 1 step away. Since neither ghost can reach the target as fast as you, you can escape, so the answer is True.

Step-by-step:

• Compute your distance: 1
• Check ghost 1: 2 > 1 (safe)
• Check ghost 2: 2 > 1 (safe)
• No ghost can reach as fast as you, return True

Time and Space Complexity

Brute-force Approach:
If you tried to simulate every possible move for you and each ghost, the number of possible states would grow exponentially, making it infeasible for large inputs.

Optimized Approach:
The optimized solution only requires:

• Calculating your distance: O(1)
• Looping through each ghost: O(N), where N is the number of ghosts

Time Complexity: O(N), since we check each ghost once.
Space Complexity: O(1), since we use only a few variables and don't store extra data.

Summary

The "Escape The Ghosts" problem is elegantly solved by focusing on the minimum steps (Manhattan distance) required for you and each ghost to reach the target. By comparing these distances, we avoid unnecessary simulations and achieve an efficient O(N) solution. The key insight is recognizing that the optimal path for all parties is always the shortest possible, making the problem a simple comparison rather than a complex pathfinding challenge.