789. Escape The Ghosts

MediumArrayMath
Leetcode Link

Problem Description

In this game, you're playing a version of PAC-MAN where you're trying to reach a specific target point on an infinite 2-D grid, while avoiding being caught by ghosts. You start at [0, 0] and your target location is given by [x_target, y_target]. Ghosts are placed on the grid, and their starting positions are given in a 2D array ghosts, where each entry ghosts[i] represents the starting position [xi, yi] of the i-th ghost.

On every turn, both you and the ghosts can choose one of the following actions: move one unit north, south, east, or west, or stay still. The key is that all moves happen at the same time. You can only safely reach your target if you can get there before any ghost can reach you. If you reach the target or any square at the same time as a ghost, you do not escape and you lose the game.

Your task is to determine if it's possible for you to reach the target before any of the ghosts can get to you, under any circumstances. If you can always reach the target no matter how the ghosts move, you should return true, otherwise, you should return false.

Intuition

The intuition behind the solution is based on comparing distances. Since the grid is infinite and you and the ghosts move simultaneously, the only way a ghost can catch you is if it is closer to the target than you are, or if it gets to your path before you reach your target. If you are closer to the target than any of the ghosts, then you can always reach the target first by moving directly towards it.

The solution leverages the Manhattan distance, which in a grid layout is the sum of the horizontal and vertical distances. Our PAC-MAN character can reach the target if the Manhattan distance from [0, 0] to the target is less than the Manhattan distance from any ghost's starting position to the target. This is because if our character is closer, no matter how the ghosts move, they cannot reach the target before our character does. The code therefore calculates the Manhattan distance from the start to the target, which is abs(tx) + abs(ty), and compares it with the Manhattan distance from each ghost to the target abs(tx - x) + abs(ty - y).

If for every ghost, the ghost's distance to the target is greater than your distance to the target, then you can escape, and the function returns true; otherwise, at least one ghost can reach the target quicker or at the same time as you, and you cannot escape, meaning the function should return false.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Solution Approach

The implementation of the solution uses a simple loop to iterate through each ghost's position in the ghosts array. It then applies the Manhattan distance formula to compare the distance of each ghost from the target with your distance from the target.

Algorithms & Formulas

No advanced algorithms are used in this solution. The code hinges on the understanding and application of the Manhattan distance in a grid. The Manhattan distance D between two points (x1, y1) and (x2, y2) is calculated as:

1D = |x2 - x1| + |y2 - y1|

where |.| denotes the absolute value. This distance calculation assumes that you can only move along grid lines (no diagonal movement).

Data Structures

The provided solution does not utilize any complex data structures; it simply iterates over the list of ghosts' locations.

Patterns

The key pattern here is a direct comparison within a loop that terminates early if any ghost is too close to the target. The Python built-in function all() is used to compact the pattern into a single expression.

Code Walkthrough

  • tx, ty = target extracts the target coordinates.
  • The expression abs(tx - x) + abs(ty - y) computes the Manhattan distance from each ghost's starting position to the target.
  • abs(tx) + abs(ty) gives your Manhattan distance to the target from the starting point [0, 0].
  • The all() function is used to check if, for all ghosts, the ghost's Manhattan distance to the target is greater than your Manhattan distance to the target.
  • If the condition is true for all ghosts, the result is true, indicating escape is possible; otherwise, it's false.

In summary, the solution approach is to use a simple distance comparison strategy, verifying that you are closer to the target than any of the ghosts, allowing for a possible escape.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

Example Walkthrough

Let's say we have a target location at [4, 3] and there are two ghosts located at [3, 0] and at [2, 5]. To illustrate the solution approach:

  1. Calculate our Manhattan distance to the target. Since we start at [0, 0], our distance to the target at [4, 3] is |4 - 0| + |3 - 0| = 4 + 3 = 7.

  2. Now, we compute the Manhattan distances for each ghost to the target:

    • For the first ghost at [3, 0], the distance to the target [4, 3] is |4 - 3| + |3 - 0| = 1 + 3 = 4.
    • For the second ghost at [2, 5], the distance to the target [4, 3] is |4 - 2| + |3 - 5| = 2 + 2 = 4.

  3. Compare our distance to each ghost's distance to the target:

    • Our distance to the target is 7, which is greater than both ghost 1 and ghost 2's distance to the target (4 and 4 respectively). In this case, at least one ghost (in this example actually both) could reach the target faster than we can or at the same time if moving optimally.

  4. Following the solution approach, since at least one ghost's Manhattan distance is less than or equal to ours, we cannot guarantee reaching the target first. Therefore, the function would return false indicating that escape is not possible under these conditions.

Solution Implementation

1from typing import List
2
3class Solution:
4    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
5        # Unpacking the target's x and y coordinates
6        target_x, target_y = target
7      
8        # Check if distance from each ghost to the target is greater than
9        # the distance from player's starting point (0, 0) to the target.
10        # If true for all ghosts, then escape is possible.
11        return all(
12            abs(target_x - ghost_x) + abs(target_y - ghost_y) > abs(target_x) + abs(target_y)
13            for ghost_x, ghost_y in ghosts
14        )
15        # This comparison uses the Manhattan distance, which is the sum of the
16        # absolute differences along each dimension (x and y in this case).
17
18# Here, abs function is used to calculate the absolute value which is required
19# to measure the Manhattan distance.
20# The all function is used to ensure the condition must be true for all ghosts in the list.
21
1class Solution {
2    public boolean escapeGhosts(int[][] ghosts, int[] target) {
3        // Store the target position coordinates for easier access
4        int targetX = target[0];
5        int targetY = target[1];
6      
7        // Go through all the ghost positions to determine if you can escape.
8        for (int[] ghost : ghosts) {
9            // Store ghost position coordinates for easier access
10            int ghostX = ghost[0];
11            int ghostY = ghost[1];
12
13            // Calculate the Manhattan distance from the ghost to the target
14            int ghostToTargetDistance = Math.abs(targetX - ghostX) + Math.abs(targetY - ghostY);
15            // Calculate the Manhattan distance from the origin to the target
16            int originToTargetDistance = Math.abs(targetX) + Math.abs(targetY);
17
18            // If any ghost can reach the target quicker or at the same time as you can from the origin,
19            // you cannot escape; return false.
20            if (ghostToTargetDistance <= originToTargetDistance) {
21                return false;
22            }
23        }
24      
25        // If none of the ghosts can reach the target quicker than you can from the origin,
26        // you can escape; return true.
27        return true;
28    }
29}
30
1class Solution {
2public:
3    // Function to determine if it's possible to escape ghosts and reach the target
4    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
5        // Store the target coordinates for easier access
6        int targetX = target[0];
7        int targetY = target[1];
8      
9        // Iterate through the list of ghosts
10        for (auto& ghost : ghosts) {
11            // Store the ghost's coordinates for easier access
12            int ghostX = ghost[0];
13            int ghostY = ghost[1];
14          
15            // Calculate the Manhattan distance from the ghost to the target
16            int ghostToTargetDistance = abs(targetX - ghostX) + abs(targetY - ghostY);
17          
18            // Calculate the Manhattan distance from the player's start position (0,0) to the target
19            int playerToTargetDistance = abs(targetX) + abs(targetY);
20          
21            // If any ghost can reach the target sooner or at the same time as the player,
22            // it's not possible to escape, return false
23            if (ghostToTargetDistance <= playerToTargetDistance) {
24                return false;
25            }
26        }
27      
28        // If no ghost can reach the target sooner than the player, it's possible to escape, return true
29        return true;
30    }
31};
32
1/**
2 * Determines if the player can escape without any ghost reaching the target first.
3 * @param ghosts - Array of positions of the ghosts, where each position is represented as an [x, y] tuple.
4 * @param target - The target destination as an [x, y] tuple.
5 * @returns boolean - true if the player can escape, otherwise false.
6 */
7function escapeGhosts(ghosts: number[][], target: number[]): boolean {
8    // Destructure target coordinates into targetX and targetY for clarity.
9    const [targetX, targetY] = target;
10
11    // Loop over each ghost's position.
12    for (const [ghostX, ghostY] of ghosts) {
13        // Calculate the Manhattan distance from the ghost to the target.
14        const ghostDistance = Math.abs(targetX - ghostX) + Math.abs(targetY - ghostY);
15        // Calculate the Manhattan distance from the player's starting point (0, 0) to the target.
16        const playerDistance = Math.abs(targetX) + Math.abs(targetY);
17      
18        // If a ghost can reach the target in a distance that's less than or
19        // equal to the player's distance to the target, the player cannot escape.
20        if (ghostDistance <= playerDistance) {
21            return false;
22        }
23    }
24
25    // If no ghost can reach the target before the player, the player can escape.
26    return true;
27}
28
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

The provided Python code calculates whether a player can escape from all the ghosts to reach a target position on a grid.

Time Complexity:

The time complexity of this code is O(n), where n is the number of ghosts. This is because the code iterates through the list of ghosts once, computing the Manhattan distance between each ghost and both the target and origin point (0,0). The all function continues until it finds a ghost who can reach the target before the player or until it has checked all ghosts.

Space Complexity:

The space complexity of the code is O(1). The space used does not grow with the input size (number of ghosts) since no additional data structures are utilized that depend on the number of ghosts. The variables tx and ty are used to store the coordinates of the target, but these use a constant amount of space. The space for the input list of ghosts and the target point is not counted, as these are inputs and not extra space used for processing.

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

Fast Track Your Learning with Our Quick Skills Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫