algoadvance

Leetcode 789. Escape The Ghosts

Problem Statement

You are playing a simplified PAC-MAN game. You start at the point (0, 0) on an infinite 2D grid and your destination is the point target. There are several ghosts on the same 2D grid, each represented as a point in a 2D array ghosts. Each turn, you and all the ghosts may independently choose to move either north, south, east, or west by one unit.

You escape if and only if you can reach the target before any ghost can reach you. If you reach the target at the same time as a ghost, it is considered that the ghost catches you.

Return true if it is possible to escape all ghosts or false otherwise.

Example:

• Input: ghosts = [[1, 0], [0, 3]], target = [0, 1]

• Output: true

• Input: ghosts = [[1, 0]], target = [2, 0]
• Output: false

Strategy

1. Distance Calculation:
   • The key observation is that if you can reach the target point faster than any ghost, then you can escape. Otherwise, you cannot.
   • The distance from the starting point (0, 0) to the target is simply the Manhattan distance: |target[0]| + |target[1]|.
2. Ghosts’ Distance:
   • Similarly, calculate the Manhattan distance from each ghost’s position to the target.
3. Comparison:
   • Compare your distance to the target with each ghost’s distance to the target.
   • If any ghost’s distance to the target is less than or equal to your distance, you cannot escape.

Clarifying Questions

1. Boundary Conditions: Are all the coordinates within a certain limit or any constraints like maximum value for coordinates?
2. Multiple Ghosts: How to handle multiple ghosts? Just need to check if any ghost reaches before or at the same time as you?
3. Edge Cases: Consider edge cases such as:
   • Target is the same as the starting point (0, 0).
   • No ghosts available.

Code

Here’s how we can implement this logic in C++:

#include <vector>
#include <cmath>

using namespace std;

class Solution {
public:
    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
        // Calculate the distance from the start point (0, 0) to the target
        int playerDistance = abs(target[0]) + abs(target[1]);

        // Check each ghost's distance to the target
        for (const auto& ghost : ghosts) {
            int ghostDistance = abs(ghost[0] - target[0]) + abs(ghost[1] - target[1]);
            if (ghostDistance <= playerDistance) {
                // If any ghost can reach the target at the same time or faster, you can't escape
                return false;
            }
        }

        // If no ghosts can reach the target faster or at the same time, you can escape
        return true;
    }
};

Time Complexity

• Time Complexity: The algorithm iterates over each ghost exactly once and performs a constant amount of work for each iteration (calculating Manhattan distance). Thus, the time complexity is (O(n)), where (n) is the number of ghosts.
• Space Complexity: The space complexity is (O(1)) since we only use a fixed amount of additional space for storing distances and comparisons.

This solution efficiently determines if you can escape from all ghosts based on their distances to the target relative to yours.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?