algoadvance

Leetcode 789. Escape The Ghosts

Problem Statement

You are playing a simplified PAC-MAN game. You start at the point (0, 0) and your destination is at point (target[0], target[1]). There are several ghosts on the map, and each ghost starts at some starting point (ghosts[i][0], ghosts[i][1]).

Each turn, you and all the ghosts simultaneously may move in one of the four cardinal directions: north, south, east, or west (moving from (x, y) to (x + 1, y), (x - 1, y), (x, y + 1), or (x, y - 1)). You escape if and only if you can reach the target before any ghosts can capture you (i.e., land on you).

Given an array ghosts, where ghosts[i] is the starting position of the i-th ghost, and an array target, return true if it is possible to escape without being captured by any ghosts, otherwise return false.

Example 1:

Input: ghosts = [[1, 0], [0, 3]], target = [0, 1]
Output: true
Explanation: You can reach the destination (0, 1) right before the ghost at (1, 0) moves there.

Example 2:

Input: ghosts = [[1, 0]], target = [2, 0]
Output: false
Explanation: The ghost can reach the target at the same time as you.

Clarifying Questions

  1. Can multiple ghosts occupy the same position?
    • Yes, that can be assumed.
  2. What are the movement constraints?
    • Both you and the ghosts can move to the four cardinal directions, and per turn, each can move exactly one unit.
  3. How do ghosts capture you?
    • A ghost captures you by landing on the same cell as you.
  4. What if the player’s starting point is the same as the target?
    • You have already escaped since you reached the target. Return true.

Strategy

  1. Distance Calculation:
    • Use Manhattan distance to determine the number of steps required for both player and ghosts to reach the target.
  2. Escape Condition:
    • You can escape if the distance for each ghost to the target is greater than the distance for you.

Code

Here is the Java code implementing the strategy:

public class EscapeTheGhosts {
    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int playerDistance = Math.abs(target[0]) + Math.abs(target[1]);

        // Check the distance of each ghost to the target
        for (int[] ghost : ghosts) {
            int ghostDistance = Math.abs(ghost[0] - target[0]) + Math.abs(ghost[1] - target[1]);
            if (ghostDistance <= playerDistance) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        EscapeTheGhosts solution = new EscapeTheGhosts();

        // Test case 1
        int[][] ghosts1 = // use example above
        int[] target1 = {0, 1};
        System.out.println(solution.escapeGhosts(ghosts1, target1)); // Output: true

        // Test case 2
        int[][] ghosts2 = // use example above
        int[] target2 = {2, 0};
        System.out.println(solution.escapeGhosts(ghosts2, target2)); // Output: false
    }
}

Time Complexity

This solution efficiently checks for the escape condition by leveraging the properties of Manhattan distance and comparative speed to the target.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI