How do you solve Escape The Ghosts on LeetCode?

Escape The Ghosts (LeetCode #789) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The distance metric used is Manhattan distance, which is suitable for grid-based movement.

What is the brute force solution for Escape The Ghosts?

The brute force approach for Escape The Ghosts is Brute Force, with O(n) time complexity and O(1) space complexity. In the brute-force approach, we calculate the distance from the starting point to the target and compare it with the distance from each ghost to the target. If any ghost can reach the target at the same time or before you, you cannot escape. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Escape The Ghosts?

Escape The Ghosts uses the following concepts: Array, Math. The recommended patterns to study are: Distance Calculation, Grid Traversal.

What are the interview tips for Escape The Ghosts?

Always clarify the movement rules and how distances are calculated. Discuss edge cases, such as ghosts starting at the target or very close to it. Practice explaining your thought process clearly, as communication is key in interviews.

What are common mistakes when solving Escape The Ghosts?

Confusing the distance calculation; remember to use Manhattan distance for grid movement. Not considering the case where ghosts can reach the target at the same time.

#789

Escape The Ghosts

Medium

ArrayMathDistance CalculationGrid Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution is essentially the same as the brute-force approach but emphasizes the efficiency of checking distances directly, ensuring we minimize unnecessary calculations.

⚙️

Algorithm

4 steps

1Step 1: Calculate the Manhattan distance from the starting point [0, 0] to the target [x_target, y_target].
2Step 2: Initialize a variable to track the player's distance to the target.
3Step 3: For each ghost, calculate its distance to the target and compare it with the player's distance.
4Step 4: If any ghost's distance is less than or equal to the player's distance, return false. Otherwise, return true.

solution.py3 lines

1def escapeGhosts(ghosts, target):
2    player_distance = abs(target[0]) + abs(target[1])
3    return all(abs(ghost[0] - target[0]) + abs(ghost[1] - target[1]) > player_distance for ghost in ghosts)

ℹ

Complexity note: The time complexity remains O(n) as we still iterate through each ghost, and the space complexity is O(1) since we only store a few variables.

1The distance metric used is Manhattan distance, which is suitable for grid-based movement.
2Simultaneous movement means we need to consider the worst-case scenario for the ghosts.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.