Problem Description

You're playing a PAC-MAN style game on an infinite 2D grid. You start at position [0, 0] and need to reach a target position [x_target, y_target]. There are ghosts on the grid, each starting at their own positions given in the array ghosts, where ghosts[i] = [x_i, y_i] represents the starting position of the i-th ghost.

The game works as follows:

• Each turn, both you and all ghosts can choose to either:
  • Move 1 unit in any cardinal direction (north, east, south, or west)
  • Stay still
• All movements happen simultaneously

You successfully escape if you reach the target position before any ghost can reach you. If you and a ghost arrive at the same position (including the target) at the same time, you do not escape.

The problem asks you to determine if it's possible for you to escape regardless of how the ghosts move. Return true if you can guarantee your escape, false otherwise.

The key insight is that since ghosts can move optimally, they will always take the shortest path to intercept you. The solution uses Manhattan distance to check if any ghost can reach the target faster than or at the same time as you. If your Manhattan distance to the target (|target_x| + |target_y|) is less than any ghost's Manhattan distance to the target (|target_x - ghost_x| + |target_y - ghost_y|), then you can escape. Otherwise, a ghost can always intercept you at or before the target.

Intuition

At first glance, this problem might seem complex - we need to consider all possible paths we could take and all possible moves the ghosts could make. However, let's think about what the optimal strategy for both parties would be.

Since the ghosts want to catch us, their best strategy is to move directly toward wherever we're trying to go. And since we're trying to reach the target, our best path is to move directly toward the target as well.

Here's the crucial realization: If a ghost can reach the target position in the same or fewer moves than we can, that ghost can always intercept us. Why? Because:

1. No matter what path we take to the target, we need at least manhattan_distance moves to get there (the Manhattan distance being |target_x| + |target_y| from our starting position [0, 0]).

2. If a ghost can reach the target in equal or fewer moves, it can simply head straight to the target and wait for us there. Even if we try to take a detour, we'll eventually need to reach the target, and the ghost will be there.

3. The ghost doesn't need to chase us around the grid - it just needs to get to our destination before or at the same time as us.

Therefore, the problem simplifies to checking: Can we reach the target in fewer moves than any ghost can?

Our distance to target: |target_x - 0| + |target_y - 0| = |target_x| + |target_y|

Each ghost's distance to target: |target_x - ghost_x| + |target_y - ghost_y|

We can escape if and only if our distance is strictly less than every ghost's distance to the target. This is why the solution checks that all ghosts have a greater Manhattan distance to the target than we do.

Learn more about Math patterns.

Solution Approach

The implementation is elegantly simple once we understand the key insight about Manhattan distances:

1. Extract the target coordinates: We first unpack the target position into tx and ty for easier reference.

2. Calculate our distance to target: Since we start at [0, 0], our Manhattan distance to the target is simply |tx| + |ty|, which equals abs(tx) + abs(ty).

3. Check each ghost's distance: For each ghost at position [x, y], we calculate its Manhattan distance to the target as abs(tx - x) + abs(ty - y).

4. Compare distances: We use Python's all() function to verify that every ghost has a strictly greater distance to the target than we do. The condition abs(tx - x) + abs(ty - y) > abs(tx) + abs(ty) must be true for all ghosts.

The solution uses a generator expression inside all() to efficiently check this condition for each ghost:

all(abs(tx - x) + abs(ty - y) > abs(tx) + abs(ty) for x, y in ghosts)

This returns:

• True if all ghosts are farther from the target than we are (we can escape)
• False if at least one ghost can reach the target as fast or faster than us (we cannot escape)

The time complexity is O(n) where n is the number of ghosts, as we need to check each ghost once. The space complexity is O(1) since we only use a constant amount of extra space regardless of the input size.

Example Walkthrough

Let's walk through a concrete example to see how the Manhattan distance solution works.

Example 1:

• Target: [2, 3]
• Ghosts: [[1, 0], [4, 3]]

Step 1: Calculate our distance to the target

• We start at [0, 0]
• Our Manhattan distance = |2 - 0| + |3 - 0| = 2 + 3 = 5
• We need exactly 5 moves to reach the target (for example: right, right, up, up, up)

Step 2: Calculate each ghost's distance to the target

• Ghost 1 at [1, 0]:

  • Distance = |2 - 1| + |3 - 0| = 1 + 3 = 4
  • This ghost needs only 4 moves to reach the target

• Ghost 2 at [4, 3]:

  • Distance = |2 - 4| + |3 - 3| = 2 + 0 = 2
  • This ghost needs only 2 moves to reach the target

Step 3: Compare distances

• Our distance: 5 moves
• Ghost 1 distance: 4 moves (4 < 5, ghost is closer!)
• Ghost 2 distance: 2 moves (2 < 5, ghost is closer!)

Since both ghosts can reach the target faster than us, we cannot escape. The function returns False.

Example 2:

• Target: [1, 1]
• Ghosts: [[2, 3], [-1, 2]]

Step 1: Calculate our distance

• Our Manhattan distance = |1| + |1| = 2

Step 2: Calculate ghost distances

• Ghost 1 at [2, 3]: Distance = |1 - 2| + |1 - 3| = 1 + 2 = 3
• Ghost 2 at [-1, 2]: Distance = |1 - (-1)| + |1 - 2| = 2 + 1 = 3

Step 3: Compare

• Our distance: 2 moves
• Ghost 1: 3 moves (3 > 2, we're closer!)
• Ghost 2: 3 moves (3 > 2, we're closer!)

Since we can reach the target before any ghost, we can escape. The function returns True.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of ghosts in the input list. The algorithm iterates through each ghost exactly once to calculate the Manhattan distance from that ghost to the target and compare it with the player's Manhattan distance to the target. Each distance calculation takes O(1) time (simple arithmetic operations), so the overall time complexity is linear with respect to the number of ghosts.

Space Complexity: O(1). The algorithm only uses a constant amount of extra space regardless of the input size. The variables tx and ty store the target coordinates, and the generator expression in the all() function processes one ghost at a time without storing intermediate results. No additional data structures are created that scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Overthinking Movement Strategies

Many developers initially try to simulate actual movement paths or implement complex pathfinding algorithms like BFS/DFS to track all possible moves. This leads to unnecessarily complex solutions that consider intermediate positions and collision scenarios.

Why it's wrong: The problem seems to require tracking movements, but the key insight is that both the player and ghosts will take optimal paths. Since the grid is infinite and obstacle-free, the optimal path is always the direct Manhattan path to the target.

Correct approach: Simply compare Manhattan distances. If a ghost can reach the target in equal or fewer steps, it will go directly there and wait, guaranteeing an interception.

2. Misunderstanding Simultaneous Movement

Some solutions incorrectly assume that the player moves first, then ghosts move, or vice versa. This can lead to checking if the player can "outrun" ghosts along the path.

Why it's wrong: All entities move simultaneously each turn. This means we can't gain an advantage by moving first or analyzing turn-by-turn positions.

Correct approach: Focus only on the final destination. Since movements are simultaneous, what matters is who can reach the target first, not the intermediate positions.

3. Incorrect Distance Calculation

A common error is using Euclidean distance sqrt((x2-x1)² + (y2-y1)²) instead of Manhattan distance, or forgetting to use absolute values.

Wrong implementation:

# Incorrect - using Euclidean distance
player_distance = math.sqrt(target_x**2 + target_y**2)

# Incorrect - missing absolute values
player_distance = target_x + target_y

Correct implementation:

player_distance = abs(target_x) + abs(target_y)
ghost_distance = abs(target_x - ghost_x) + abs(target_y - ghost_y)

4. Off-by-One Error in Comparison

Using < instead of <= when comparing distances, thinking the player wins ties.

Wrong:

if ghost_distance < player_distance:  # Wrong - should be <=
    return False

Correct:

if ghost_distance <= player_distance:  # Ghost wins on ties
    return False

The problem explicitly states: "If you and a ghost arrive at the same position at the same time, you do not escape."