# LeetCode 789: Escape The Ghosts

## Problem Restatement

We start at point:

```python
[0, 0]
```

We want to reach:

```python
target = [target_x, target_y]
```

There are several ghosts. Each ghost starts at:

```python
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:

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

## Examples

Example 1:

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

Our distance to the target is:

```python
abs(0) + abs(1) = 1
```

The ghosts need `2` steps to reach the target.

We arrive first, so the answer is:

```python
True
```

Example 2:

```python
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:

```python
False
```

Example 3:

```python
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:

```python
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:

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

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

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

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

```python
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

```python
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:

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

Then we check each ghost:

```python
for ghost_x, ghost_y in ghosts:
```

The ghost's shortest time to the target is:

```python
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:

```python
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:

```python
return True
```

## Testing

```python
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 |