LeetCode 789: Escape The Ghosts

Problem Restatement

We start at point:

[0, 0]

We want to reach:

target = [target_x, target_y]

There are several ghosts. Each ghost starts at:

ghosts[i] = [ghost_x, ghost_y]

Each turn, we and all ghosts may move one step north, south, east, or west. Everyone moves at the same speed.

We escape only if we reach the target before any ghost can reach us. If we and a ghost arrive at the same square at the same time, including the target, we do not escape.

Input and Output

Item	Meaning
Input	ghosts, a list of ghost positions, and target
Output	True if escape is possible, otherwise False
Start position	We start at [0, 0]
Movement	One step in one of four cardinal directions per turn
Tie rule	If a ghost reaches the same square at the same time, escape fails

Function shape:

class Solution:
    def escapeGhosts(self, ghosts: list[list[int]], target: list[int]) -> bool:
        ...

Examples

Example 1:

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

Our distance to the target is:

abs(0) + abs(1) = 1

The ghosts need 2 steps to reach the target.

We arrive first, so the answer is:

True

Example 2:

ghosts = [[1, 0]]
target = [2, 0]

Our distance to the target is 2.

The ghost's distance to the target is 1.

The ghost can reach the target first, so the answer is:

False

Example 3:

ghosts = [[2, 0]]
target = [1, 0]

Our distance to the target is 1.

The ghost's distance to the target is also 1.

A tie does not count as escape, so the answer is:

False

First Thought: Simulate Movement

A direct idea is to simulate every possible move.

At each turn:

1. We can move in four directions.
2. Each ghost can also move in four directions.
3. We check whether we can reach the target safely.

This becomes complicated quickly. There are many possible paths, and ghosts are adversarial.

We do not need simulation because movement on this grid has a simple shortest-path distance.

Key Insight

The shortest number of steps between two grid points is the Manhattan distance:

abs(x1 - x2) + abs(y1 - y2)

We start at [0, 0], so our minimum time to reach the target is:

abs(target[0]) + abs(target[1])

For a ghost at [gx, gy], its minimum time to reach the target is:

abs(gx - target[0]) + abs(gy - target[1])

If any ghost can reach the target in the same number of steps or fewer, then escape is impossible.

Why checking the target is enough: if a ghost can arrive at the target no later than us, it can block us there. If every ghost needs strictly more steps than us to reach the target, we can go directly to the target and arrive first.

Algorithm

1. Compute our distance from [0, 0] to target.
2. For each ghost:
   1. Compute the ghost's distance to target.
   2. If the ghost distance is less than or equal to our distance, return False.
3. If no ghost can reach the target as fast as us, return True.

Correctness

Our fastest possible route to the target takes the Manhattan distance from [0, 0] to target, because each move changes one coordinate by exactly one.

A ghost's fastest possible route to the target is also its Manhattan distance to the target.

If some ghost has distance less than or equal to our distance, that ghost can reach the target before us or at the same time. Since reaching the same square at the same time does not count as escape, we cannot escape.

If every ghost has distance strictly greater than our distance, then we take any shortest path directly to the target. We arrive before every ghost can reach the target. Since ghosts cannot move faster than one grid step per turn, none can force a successful interception before that target arrival. Therefore, escape is possible.

Complexity

Let g = len(ghosts).

Metric	Value	Why
Time	O(g)	We check each ghost once
Space	O(1)	We store only a few integers

Implementation

class Solution:
    def escapeGhosts(self, ghosts: list[list[int]], target: list[int]) -> bool:
        player_distance = abs(target[0]) + abs(target[1])

        for ghost_x, ghost_y in ghosts:
            ghost_distance = abs(ghost_x - target[0]) + abs(ghost_y - target[1])

            if ghost_distance <= player_distance:
                return False

        return True

Code Explanation

We compute our shortest time to the target:

player_distance = abs(target[0]) + abs(target[1])

Then we check each ghost:

for ghost_x, ghost_y in ghosts:

The ghost's shortest time to the target is:

ghost_distance = abs(ghost_x - target[0]) + abs(ghost_y - target[1])

If the ghost can reach the target no later than us, we fail:

if ghost_distance <= player_distance:
    return False

The <= is important because ties are losing.

If every ghost is strictly farther away from the target, we escape:

return True

Testing

def run_tests():
    s = Solution()

    assert s.escapeGhosts([[1, 0], [0, 3]], [0, 1]) is True
    assert s.escapeGhosts([[1, 0]], [2, 0]) is False
    assert s.escapeGhosts([[2, 0]], [1, 0]) is False

    assert s.escapeGhosts([], [5, 5]) is True
    assert s.escapeGhosts([[10, 10]], [1, 1]) is True
    assert s.escapeGhosts([[1, 1]], [2, 0]) is False
    assert s.escapeGhosts([[-1, 0]], [-2, 0]) is False

    print("all tests passed")

run_tests()

Test coverage:

Test	Why
Ghosts farther than player	Escape is possible
Ghost closer to target	Escape is impossible
Ghost ties player	Tie is losing
No ghosts	Always safe
Negative coordinates	Manhattan distance works in all directions
Ghost reaches target at same time	Checks <= condition