Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Escape The Ghosts solution and explanation

MediumArrayMath5 min read64.2% acceptanceUpdated 9 Apr 2026
Asked atWixGoogle
Practise Escape The Ghosts
5:03
Escape The Ghosts || leetcode 789 || leetcode medium || c++ solutioncode Explainer · 5:03 · 1K viewsWatch on YouTube
7 more videos on this problem
  1. Escape The Ghosts || leetcode 789 || leetcode medium || c++ solutioncode Explainer · 5:03 · 1K views
  2. 789. Escape The Ghosts (Leetcode Medium)Programming Live with Larry · 7:24 · 962 views
  3. LeetCode 789. Escape The Ghosts Solution Explained - JavaAlgorithms and Data Structures Course · 7:40 · 319 views
  4. 789 Escape The GhostsMath Geeks · 2:17 · 106 views
  5. Leetcode 789 Escape The Ghosts - Interesting Coding Question - Logic Explained In HindiAlgorithmicIQ · 17:30 · 20 views
  6. No Sound Leetcode 789: Escape The GhostsExtremeProgrammer · 1:04 · 19 views
  7. 【Leetcode III 91/100】789. Escape The Ghosts (~Medium)思臉AI · 2:01 · 13 views
  8. LeetCode 789: Escape The GhostsAlitaCode · 25:33 · 5 views

The problem

You are playing a simplified PAC-MAN game on an infinite 2-D grid. You start at the point [0, 0], and you are given a destination point target = [xtarget, ytarget] that you are trying to get to. There are several ghosts on the map with their starting positions given as a 2D array ghosts, where ghosts[i] = [xi, yi] represents the starting position of the ith ghost. All inputs are integral coordinates.

Each turn, you and all the ghosts may independently choose to either move 1 unit in any of the four cardinal directions: north, east, south, or west, or stay still. All actions happen simultaneously.

You escape if and only if you can reach the target before any ghost reaches you. If you reach any square (including the target) at the same time as a ghost, it does not count as an escape.

Return true if it is possible to escape regardless of how the ghosts move, otherwise return false.

Example 1:

Input: ghosts = [[1,0],[0,3]], target = [0,1]
Output: true
Explanation: You can reach the destination (0, 1) after 1 turn, while the ghosts located at (1, 0) and (0, 3) cannot catch up with you.

Example 2:

Input: ghosts = [[1,0]], target = [2,0]
Output: false
Explanation: You need to reach the destination (2, 0), but the ghost at (1, 0) lies between you and the destination.

Example 3:

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

Constraints:

  • 1 <= ghosts.length <= 100
  • ghosts[i].length == 2
  • -104 <= xi, yi <= 104
  • There can be multiple ghosts in the same location.
  • target.length == 2
  • -104 <= xtarget, ytarget <= 104

Approach overview

Problem Overview: You start at (0,0) on an infinite grid and want to reach a target coordinate. Several ghosts start at different positions and can move one step per turn in the four cardinal directions. If any ghost reaches the target at the same time or earlier than you, escape becomes impossible. The task is to determine whether you can guarantee reaching the target before any ghost intercepts.

Approach 1: Brute Force Simulation (Exponential Time, O(k) Space)

A direct idea is to simulate movement on the grid. From (0,0), explore all possible paths toward the target using BFS or DFS while simultaneously tracking ghost positions at each time step. At every move, check whether a ghost can reach the same cell at the same or earlier time. The grid is theoretically unbounded, so the search space grows rapidly and becomes impractical without heavy pruning. Time complexity becomes exponential in the path length, while space complexity is O(k) for storing frontier states and ghost positions.

This method demonstrates the problem mechanics but is rarely used in practice. It helps confirm that movement is symmetric in all directions and that timing is the key constraint.

Approach 2: Manhattan Distance Comparison (O(n) Time, O(1) Space)

The key observation is that the shortest path on a grid with four-directional movement equals the Manhattan distance. Your distance from the start to the target is |target_x| + |target_y|. Each ghost can also reach the target using its Manhattan distance |ghost_x - target_x| + |ghost_y - target_y|. If any ghost's distance to the target is less than or equal to yours, that ghost can intercept or reach the target at the same time.

Instead of simulating movement, iterate through the ghost positions stored in the array and compute their Manhattan distance using simple math operations. The moment a ghost distance <= your distance, escape is impossible. If every ghost is strictly farther away, you will always reach the target first.

This works because ghosts can always mirror your path or choose the optimal route on the grid. Therefore, distance alone determines the outcome. The algorithm scans the ghost list once, giving O(n) time complexity and constant O(1) extra space.

Recommended for interviews: The Manhattan Distance Comparison approach is what interviewers expect. It reduces a movement simulation problem into a simple mathematical observation. Showing the brute force idea first demonstrates problem understanding, but recognizing the Manhattan distance property shows strong algorithmic intuition.

Approach 1: Manhattan Distance Comparison

This approach calculates the Manhattan distance from the starting point (0,0) to the target for you, and for each ghost from their starting position to the target. You can only escape if your distance to the target is strictly less than every ghost's distance to the target, meaning you reach the destination before any ghost can get there.

class Solution:
    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
        player_dist = abs(target[0]) + abs(target[1])
        for ghost in ghosts:
            ghost_dist = abs(ghost[0] - target[0]) + abs(ghost[1] - target[1])
            if ghost_dist <= player_dist:
                return False
        return True
class Solution {
    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int playerDist = Math.abs(target[0]) + Math.abs(target[1]);
        for (int[] ghost : ghosts) {
            int ghostDist = Math.abs(ghost[0] - target[0]) + Math.abs(ghost[1] - target[1]);
            if (ghostDist <= playerDist) {
                return false;
            }
        }
        return true;
    }
}
#include <vector>
#include <cstdlib>

using namespace std;

class Solution {
public:
    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
        int playerDist = abs(target[0]) + abs(target[1]);
        for (const vector<int>& ghost : ghosts) {
            int ghostDist = abs(ghost[0] - target[0]) + abs(ghost[1] - target[1]);
            if (ghostDist <= playerDist) {
                return false;
            }
        }
        return true;
    }
};
var escapeGhosts = function(ghosts, target) {
    const playerDist = Math.abs(target[0]) + Math.abs(target[1]);
    for (let ghost of ghosts) {
        const ghostDist = Math.abs(ghost[0] - target[0]) + Math.abs(ghost[1] - target[1]);
        if (ghostDist <= playerDist) {
            return false;
        }
    }
    return true;
};
#include <stdbool.h>
#include <stdlib.h>

int manhattanDistance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

bool escapeGhosts(int** ghosts, int ghostsSize, int* ghostsColSize, int* target, int targetSize) {
    int playerDistance = manhattanDistance(0, 0, target[0], target[1]);
    for (int i = 0; i < ghostsSize; i++) {
        int ghostDistance = manhattanDistance(ghosts[i][0], ghosts[i][1], target[0], target[1]);
        if (ghostDistance <= playerDistance) {
            return false;
        }
    }
    return true;
}
public class Solution {
    public bool EscapeGhosts(int[][] ghosts, int[] target) {
        int playerDist = Math.Abs(target[0]) + Math.Abs(target[1]);
        foreach (int[] ghost in ghosts) {
            int ghostDist = Math.Abs(ghost[0] - target[0]) + Math.Abs(ghost[1] - target[1]);
            if (ghostDist <= playerDist) {
                return false;
            }
        }
        return true;
    }
}

The Python implementation checks if the player can reach the destination before any ghost based on their Manhattan distances.

Complexity

Time Complexity: O(n), where n is the number of ghosts. Space Complexity: O(1).

Try this approach in the editor

Approach 2: Brute Force Simulation

This approach involves simulating every possible move for you and each ghost simultaneously. For each time step, move each entity towards the target or keep them in the same position if they're already there. This approach is generally inefficient but illustrates the problem space.

class Solution:
    def bruteForceEscape(self, ghosts: List[List[int]], target: List[int]) -> bool:
        player_dist = abs(target[0]) + abs(target[1])
        for ghost in ghosts:
            ghost_dist = abs(ghost[0] - target[0]) + abs(ghost[1] - target[1])
            if ghost_dist <= player_dist:
                return False
        return True
class Solution {
    public boolean bruteForceEscape(int[][] ghosts, int[] target) {
        int playerDist = Math.abs(target[0]) + Math.abs(target[1]);
        for (int[] ghost : ghosts) {
            int ghostDist = Math.abs(ghost[0] - target[0]) + Math.abs(ghost[1] - target[1]);
            if (ghostDist <= playerDist) {
                return false;
            }
        }
        return true;
    }
}
#include <vector>
#include <cstdlib>

using namespace std;

class Solution {
public:
    bool bruteForceEscape(vector<vector<int>>& ghosts, vector<int>& target) {
        int playerDist = abs(target[0]) + abs(target[1]);
        for (const vector<int>& ghost : ghosts) {
            int ghostDist = abs(ghost[0] - target[0]) + abs(ghost[1] - target[1]);
            if (ghostDist <= playerDist) {
                return false;
            }
        }
        return true;
    }
};
var bruteForceEscape = function(ghosts, target) {
    const playerDist = Math.abs(target[0]) + Math.abs(target[1]);
    for (let ghost of ghosts) {
        const ghostDist = Math.abs(ghost[0] - target[0]) + Math.abs(ghost[1] - target[1]);
        if (ghostDist <= playerDist) {
            return false;
        }
    }
    return true;
};
#include <stdbool.h>
#include <stdlib.h>

int manhattanDistance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

bool bruteForceEscape(int** ghosts, int ghostsSize, int* ghostsColSize, int* target, int targetSize) {
    int playerDistance = manhattanDistance(0, 0, target[0], target[1]);
    for (int i = 0; i < ghostsSize; i++) {
        int ghostDistance = manhattanDistance(ghosts[i][0], ghosts[i][1], target[0], target[1]);
        if (ghostDistance <= playerDistance) {
            return false;
        }
    }
    return true;
}
public class Solution {
    public bool BruteForceEscape(int[][] ghosts, int[] target) {
        int playerDist = Math.Abs(target[0]) + Math.Abs(target[1]);
        foreach (int[] ghost in ghosts) {
            int ghostDist = Math.Abs(ghost[0] - target[0]) + Math.Abs(ghost[1] - target[1]);
            if (ghostDist <= playerDist) {
                return false;
            }
        }
        return true;
    }
}

The function in Python approximates brute force by comparing distances. True simulation is impractical for performance reasons.

Complexity

Time Complexity: O(n), where n is the number of ghosts. Space Complexity: O(1).

Try this approach in the editor

Approach 3: Default Approach

function escapeGhosts(ghosts: number[][], target: number[]): boolean {
    const [tx, ty] = target;
    for (const [x, y] of ghosts) {
        if (Math.abs(tx - x) + Math.abs(ty - y) <= Math.abs(tx) + Math.abs(ty)) {
            return false;
        }
    }
    return true;
}
func escapeGhosts(ghosts [][]int, target []int) bool {
	tx, ty := target[0], target[1]
	for _, g := range ghosts {
		x, y := g[0], g[1]
		if abs(tx-x)+abs(ty-y) <= abs(tx)+abs(ty) {
			return false
		}
	}
	return true
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Manhattan Distance Comparison

Time Complexity: O(n), where n is the number of ghosts. Space Complexity: O(1).

Brute Force Simulation

Time Complexity: O(n), where n is the number of ghosts. Space Complexity: O(1).

Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationExponentialO(k)Useful for understanding movement rules or verifying small cases
Manhattan Distance ComparisonO(n)O(1)Optimal approach for interviews and production solutions

Frequently asked questions

Is Escape The Ghosts easy or hard?

Escape The Ghosts is generally classified as a medium problem. The implementation is simple once you recognize the Manhattan distance insight, but many candidates initially attempt unnecessary grid simulations before discovering the mathematical shortcut.

Escape The Ghosts Python/Java solution

In Python or Java, iterate through the ghosts array and compute Manhattan distance for each ghost relative to the target. Compare it with the player's distance from (0,0). If any ghost distance is smaller or equal, return false; otherwise return true after the loop.

How to solve Escape The Ghosts in O(n)?

First compute your Manhattan distance to the target: |target_x| + |target_y|. Then iterate through the ghost positions and compute each ghost's Manhattan distance to the target. If any ghost distance is less than or equal to yours, return false; otherwise return true after checking all ghosts.

What is the best approach for Escape The Ghosts?

The optimal approach uses Manhattan distance comparison. Compute your distance from (0,0) to the target and compare it with each ghost's distance to the target. If any ghost can reach the target in less than or equal steps, escape is impossible. This runs in O(n) time and O(1) space.

Is Escape The Ghosts asked at Google/Amazon/Meta?

Escape The Ghosts is a common medium-level grid reasoning problem and appears in interview preparation sets used by companies like Amazon, Google, and Meta. It tests mathematical reasoning and the ability to reduce a simulation problem into a simple distance comparison.

What data structure is used in Escape The Ghosts?

The problem primarily uses arrays to store ghost coordinates. The core logic relies on Manhattan distance calculations rather than complex data structures, making it a math-focused problem with simple iteration over the array.

What is the time complexity of Escape The Ghosts?

The optimal Manhattan distance solution runs in O(n) time where n is the number of ghosts. Each ghost requires a constant-time distance calculation. Space complexity is O(1) because no additional data structures are required.

Comments

Next problem · similarCat and Mouse IIHard
Now write it yourselfClose this page and solve Escape The Ghosts in the editor, without looking.
Practise Escape The Ghosts