Escape The Ghosts: Manhattan Distance Insight

LeetCode 789. Escape The Ghosts places you at the origin (0, 0) on a 2D grid. You want to reach a target point, but ghosts are scattered around the grid trying to catch you. Each turn, you and every ghost move one step in any cardinal direction (up, down, left, right), or stay in place. If any ghost can occupy the same cell as you at the same time (including at the target), you are caught. Can you reach the target without being caught?

At first glance, this looks like it might require BFS or game simulation. But the solution is a single comparison per ghost, no search needed.

Why this problem matters

Escape The Ghosts is a pure math insight problem. The entire challenge is recognizing that you do not need to simulate movement at all. Once you see why Manhattan distance comparison works, the code writes itself in three lines. Problems like this train you to pause before reaching for heavy algorithms and ask whether a simpler observation eliminates the need for them entirely.

The approach

The key realization: a ghost's optimal strategy is always to head directly to the target and wait there. If the ghost can reach the target in fewer or equal steps compared to you, it will always be able to catch you, no matter which path you take.

Why? Because any detour you take to avoid the ghost only makes your path longer. Meanwhile, the ghost takes the shortest path to the target. If the ghost arrives first (or at the same time), it simply waits at the target and catches you when you arrive.

This means you only need to compare Manhattan distances:

• Your distance to the target is |target[0]| + |target[1]| (since you start at the origin).
• Each ghost's distance to the target is |ghost[0] - target[0]| + |ghost[1] - target[1]|.

If every ghost has a strictly greater Manhattan distance to the target than you do, you can escape. If any ghost has a distance that is less than or equal to yours, you cannot.

Clean solution

def escape_ghosts(ghosts, target):
    player_dist = abs(target[0]) + abs(target[1])
    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

This runs in a single pass through the ghost list. No BFS, no simulation, no game tree.

Step-by-step walkthrough

The algorithm checks each ghost independently. As soon as one ghost can reach the target in time, you return False. Only if every ghost fails to beat you do you return True.

Complexity analysis

Where n is the number of ghosts. You compute one Manhattan distance per ghost and compare it to yours. No extra data structures are needed.

The building blocks

1. Manhattan distance

The Manhattan distance between two points (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|. It measures the number of grid steps needed when you can only move horizontally or vertically. This metric appears constantly in grid problems, from BFS shortest paths to clustering algorithms.

def manhattan(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

2. Greedy insight (reducing a game to a comparison)

Many problems that look like they require simulation or search actually collapse into a simple comparison once you identify the optimal strategy for all players. In this case, recognizing that the ghost's best move is always "go straight to the target" turns a game theory problem into arithmetic.

Edge cases to watch for

• Ghost already at the target: The ghost's distance is 0, which is always less than or equal to yours (unless you are also at the target, but target = [0,0] means your distance is 0 and the ghost ties, so you still cannot escape).
• Target at the origin [0, 0]: Your distance is 0. You are already there. Any ghost not at the origin has a positive distance, so you escape. But if any ghost is also at [0, 0], it catches you.
• No ghosts: The ghost list is empty. No ghost can block you, so return True.
• Ghost and player equidistant: If a ghost's distance equals yours, the ghost can reach the target at the exact same time and catch you there. Return False.
• Multiple ghosts, only one blocks: You must check all ghosts. Even if most are far away, a single close ghost is enough to block you.

From understanding to recall

Reading through this solution takes a minute. But two weeks from now, when you see a grid problem with multiple agents, will you remember to check whether a simple distance comparison is enough? That is the gap spaced repetition fills.

CodeBricks isolates the building blocks: Manhattan distance calculation and the greedy "reduce to a comparison" insight. You practice typing them from scratch at increasing intervals. After a few review cycles, reaching for Manhattan distance in grid problems becomes automatic, and you stop defaulting to BFS when arithmetic will do.

Related posts

• Reach a Number - Another math insight problem on a number line
• Robot Return to Origin - Grid movement with simple distance reasoning
• Minimum Moves to Equal Array Elements - Math insight that simplifies a seemingly complex problem