LeetCode Problem 789

Difficulty: 🟡 Medium
Topics: Array, Math

Solution

LeetCode 789 - Escape The Ghosts

Problem Understanding

This problem takes place on an infinite two dimensional grid. You begin at coordinate (0, 0) and want to reach a destination called target. At the same time, several ghosts also move on the grid from their own starting positions.

During every turn, both you and every ghost may:

• Move one unit north, south, east, or west
• Stay in place

All movements happen simultaneously.

Your goal is to determine whether you can guarantee reaching the target before any ghost can catch you. Importantly, if a ghost reaches the same position at the same time as you, you lose. This includes the target square itself.

The input consists of:

• ghosts, a list of ghost coordinates
• target, the coordinate you want to reach

The output should be:

• true if escape is always possible
• false otherwise

The key detail is that ghosts can move optimally. You are not checking whether there exists some lucky path. Instead, you must determine whether you can guarantee success regardless of how the ghosts move.

Because movement is restricted to cardinal directions, the minimum number of turns required to move between two points is the Manhattan distance.

For a point (x1, y1) and (x2, y2), the Manhattan distance is:

$|x_1-x_2|+|y_1-y_2|$

The constraints are relatively small, with at most 100 ghosts, so efficiency is not difficult to achieve. The challenge is recognizing the mathematical observation that simplifies the entire problem.

Several edge cases are important:

• A ghost may already be very close to the target.
• Multiple ghosts can share the same position.
• A ghost reaching the target at the same time as you means failure.
• Even if a ghost is not directly between you and the target, it may still block escape by arriving quickly enough.

Approaches

Brute Force Approach

A naive approach would attempt to simulate movement on the infinite grid. We could perform a breadth first search from the player's position while simultaneously tracking ghost movements.

The idea would be:

1. Generate all possible positions the player can move to.
2. Generate all possible positions ghosts can reach.
3. Continue turn by turn until:

• The player reaches the target safely, or
• A ghost intercepts the player.

This approach is theoretically correct because BFS explores states in increasing order of time. However, it becomes impractical because the grid is infinite and the number of reachable states grows extremely quickly.

Even with pruning, the state space becomes enormous because every turn introduces many new positions for both the player and the ghosts.

Key Insight

The crucial observation is that the actual path does not matter. Only the minimum arrival time matters.

Since movement is unrestricted except for cardinal directions, the shortest possible travel time between two points is simply the Manhattan distance.

Your shortest time to the target is:

$|x_t|+|y_t|$

because you start at (0,0).

Each ghost's shortest time to the target is:

$|x_i-x_t|+|y_i-y_t|$

If any ghost can reach the target in less time than or equal to your arrival time, then escape is impossible.

Why?

Because ghosts are not required to chase your exact path. They only need to intercept you somewhere. If a ghost can arrive at the target no later than you, then it can simply wait there. Since reaching the same square at the same time counts as losing, you cannot escape.

Therefore:

• If every ghost needs strictly more turns than you to reach the target, escape is guaranteed.
• Otherwise, escape is impossible.

This transforms the problem into a simple distance comparison.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential / Unbounded	Exponential / Unbounded	Simulates movement states on an infinite grid
Optimal	O(n)	O(1)	Compare Manhattan distances to target

Algorithm Walkthrough

1. Compute your minimum distance to the target.

Since you start at (0,0), your travel time is the Manhattan distance from the origin to the target. 2. Iterate through every ghost.

For each ghost position (gx, gy), compute the ghost's Manhattan distance to the target. 3. Compare the distances.

If a ghost's distance is less than or equal to your distance, immediately return False.

This means the ghost can reach the target before you or at the same time, which guarantees failure. 4. Finish checking all ghosts.

If no ghost can reach the target as quickly as you, return True.

Why it works

The correctness relies on Manhattan distance representing the minimum number of turns required to reach a position on the grid. Since both you and the ghosts move with identical speed and movement rules, only relative arrival times matter.

If a ghost can reach the target no later than you, the ghost can simply move directly there and wait. Therefore, escape becomes impossible.

If every ghost requires strictly more turns than you, then no ghost can intercept you before reaching the target, because any interception point would require at least as much travel time as reaching the target itself.

Python Solution

from typing import List

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

The implementation begins by computing the player's minimum travel time to the target using Manhattan distance from (0,0).

Next, the algorithm loops through every ghost. For each ghost, it calculates that ghost's minimum travel time to the target.

The critical comparison is:

if ghost_distance <= player_distance:

If this condition is true, the ghost can reach the target before or simultaneously with the player, so escape is impossible.

If the loop finishes without finding such a ghost, the function returns True.

The implementation uses constant extra memory because it stores only a few integer variables.

Go Solution

func escapeGhosts(ghosts [][]int, target []int) bool {
    playerDistance := abs(target[0]) + abs(target[1])

    for _, ghost := range ghosts {
        ghostDistance :=
            abs(ghost[0]-target[0]) +
                abs(ghost[1]-target[1])

        if ghostDistance <= playerDistance {
            return false
        }
    }

    return true
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

The Go implementation follows the same logic as the Python version. Since Go does not provide a built in integer absolute value function for plain int, a helper abs function is implemented manually.

The solution uses slices for the coordinate arrays and iterates through them with a range loop. Integer overflow is not a concern because coordinates are bounded by 10^4, making all distance calculations comfortably fit within Go's int type.

Worked Examples

Example 1

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

First compute the player's distance:

Calculation	Value
|0| + |1|	1

So the player needs 1 turn.

Now evaluate each ghost.

Ghost [1,0]

Calculation	Value
|1 - 0| + |0 - 1|	2

Ghost needs 2 turns.

Since 2 > 1, this ghost cannot stop the player.

Ghost [0,3]

Calculation	Value
|0 - 0| + |3 - 1|	2

Ghost needs 2 turns.

Again, 2 > 1.

No ghost can reach the target in time, so the answer is:

true

Example 2

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

Player distance:

Calculation	Value
|2| + |0|	2

Player needs 2 turns.

Ghost distance:

Calculation	Value
|1 - 2| + |0 - 0|	1

Ghost needs only 1 turn.

Since 1 <= 2, the ghost can reach the target first.

Answer:

false

Example 3

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

Player distance:

Calculation	Value
|1| + |0|	1

Ghost distance:

Calculation	Value
|2 - 1| + |0 - 0|	1

Both require exactly 1 turn.

Because arriving simultaneously means failure, the answer is:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass through all ghosts
Space	O(1)	Only a few integer variables are used

The algorithm performs a constant amount of work for each ghost, specifically a few arithmetic operations and one comparison. Since there are n ghosts, the runtime grows linearly with the number of ghosts.

No auxiliary data structures proportional to input size are allocated, so the extra memory usage remains constant.

Test Cases

from typing import List

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

solution = Solution()

# Provided example 1
assert solution.escapeGhosts([[1, 0], [0, 3]], [0, 1]) is True

# Provided example 2
assert solution.escapeGhosts([[1, 0]], [2, 0]) is False

# Provided example 3, simultaneous arrival
assert solution.escapeGhosts([[2, 0]], [1, 0]) is False

# Ghost already at target
assert solution.escapeGhosts([[5, 5]], [5, 5]) is False

# Ghost very far away
assert solution.escapeGhosts([[100, 100]], [1, 1]) is True

# Multiple ghosts, one blocks escape
assert solution.escapeGhosts([[10, 10], [1, 1], [50, 50]], [2, 2]) is False

# Negative coordinates
assert solution.escapeGhosts([[-1, -1]], [-3, -3]) is False

# Player escapes despite nearby ghost
assert solution.escapeGhosts([[1, 2]], [10, 10]) is True

# Multiple ghosts at same location
assert solution.escapeGhosts([[1, 0], [1, 0]], [3, 0]) is False

# Target adjacent to origin
assert solution.escapeGhosts([[5, 5]], [0, 1]) is True

# Large coordinate values
assert solution.escapeGhosts([[10000, -10000]], [-9999, 9999]) is False

# Ghost equally distant to target
assert solution.escapeGhosts([[0, 2]], [1, 1]) is False

Test	Why
[[1,0],[0,3]], [0,1]	Basic successful escape
[[1,0]], [2,0]	Ghost reaches target earlier
[[2,0]], [1,0]	Simultaneous arrival loses
[[5,5]], [5,5]	Ghost starts at target
[[100,100]], [1,1]	Ghost too far away
[[10,10],[1,1],[50,50]], [2,2]	One blocking ghost among many
[[-1,-1]], [-3,-3]	Negative coordinate handling
[[1,2]], [10,10]	Long successful path
[[1,0],[1,0]], [3,0]	Duplicate ghost positions
[[5,5]], [0,1]	Very short player path
[[10000,-10000]], [-9999,9999]	Constraint boundary values
[[0,2]], [1,1]	Equal Manhattan distance

Edge Cases

One important edge case occurs when a ghost can reach the target in exactly the same number of moves as the player. This is easy to mishandle if the comparison uses < instead of <=. The problem explicitly states that arriving simultaneously does not count as escaping, so the implementation correctly uses <=.

Another critical case is when a ghost already starts at the target position. In that scenario, the ghost's distance is zero, meaning the player automatically loses regardless of movement strategy. The algorithm naturally handles this because 0 <= player_distance immediately evaluates to true.

Negative coordinates are also important because Manhattan distance requires absolute values. A buggy implementation that forgets abs() would produce incorrect distances for targets or ghosts located in negative regions of the grid. The provided solution consistently uses absolute differences, ensuring correctness across all coordinate ranges.

A subtler edge case involves multiple ghosts sharing the same location. Since each ghost is evaluated independently, duplicates do not require any special handling. The algorithm simply checks every ghost's distance to the target and returns False as soon as any one ghost can intercept the player.