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

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).

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: