Escape The Ghosts - Practice Coding Problems

Escape The Ghosts - Problem

Array Math Medium

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 = [x_target, y_target] that you are trying to reach.

There are several ghosts on the map with their starting positions given as a 2D array ghosts, where ghosts[i] = [x_i, y_i] represents the starting position of the i-th ghost.

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, 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.

Input & Output

Example 1 — Ghost Blocks Escape

$ Input: ghosts = [[1,0]], target = [1,0]

› Output: false

💡 Note: Player needs 1 step to reach [1,0], but ghost is already there (0 steps). Ghost reaches target before player.

Example 2 — Successful Escape

$ Input: ghosts = [[1,0]], target = [2,0]

› Output: true

💡 Note: Player needs 2 steps to reach [2,0], ghost needs 1 step. Player can reach target before ghost intercepts.

Example 3 — Multiple Ghosts

$ Input: ghosts = [[2,0],[1,1]], target = [1,0]

› Output: false

💡 Note: Player needs 1 step. First ghost needs 1 step, second ghost needs 1 step. Ghost reaches target at same time, blocking escape.

Constraints

1 ≤ ghosts.length ≤ 100
ghosts[i].length == 2
-1000 ≤ x_i, y_i ≤ 1000
-1000 ≤ x_target, y_target ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Initial Setup

Player at [0,0], ghosts at various positions, target location

Distance Analysis

Calculate Manhattan distances for optimal paths

Escape Decision

Return true only if player is fastest to target

Key Takeaway

🎯 Key Insight: Use Manhattan distance to determine if any ghost can intercept the player's path to the target

Asked in

G Google 15 a Amazon 12 M Microsoft 8

Brief HTML summary: The key insight is to use Manhattan distance calculation. If any ghost can reach the target in equal or fewer steps than the player, escape is impossible. Best approach is Manhattan Distance with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(4^n)	O(4^n)	Simulate all possible movements for player and ghosts using BFS
Manhattan Distance	O(n)	O(1)	Compare Manhattan distances to determine if escape is possible

Brute Force Simulation — Algorithm Steps

Step 1: Initialize BFS with starting positions
Step 2: For each state, generate all possible next moves
Step 3: Check if player reaches target before ghosts

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Player at [0,0], ghosts at starting positions

BFS Expansion

Generate all possible next moves for each entity

Check Victory

Return true if player reaches target first

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int abs_val(int x) {
    return x < 0 ? -x : x;
}

bool solution(int ghosts[][2], int ghostCount, int target[2]) {
    // Convert to Manhattan distance problem
    int myDist = abs_val(target[0]) + abs_val(target[1]);
    
    // Check if any ghost can reach target faster or equal time
    for (int i = 0; i < ghostCount; i++) {
        int ghostDist = abs_val(ghosts[i][0] - target[0]) + abs_val(ghosts[i][1] - target[1]);
        if (ghostDist <= myDist) {
            return false;
        }
    }
    
    return true;
}

int main() {
    char line[1000];
    
    // Read ghosts - simple parsing
    fgets(line, sizeof(line), stdin);
    int ghosts[100][2];
    int ghostCount = 0;
    
    char* ptr = line;
    while (*ptr && ghostCount < 100) {
        if (*ptr == '[') {
            ptr++;
            while (*ptr == '[' || *ptr == ' ') ptr++;
            ghosts[ghostCount][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            if (*ptr == ',') ptr++;
            ghosts[ghostCount][1] = atoi(ptr);
            ghostCount++;
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr == ']') ptr++;
        } else {
            ptr++;
        }
    }
    
    // Read target
    fgets(line, sizeof(line), stdin);
    int target[2];
    ptr = line;
    while (*ptr && *ptr != '[') ptr++;
    if (*ptr == '[') ptr++;
    target[0] = atoi(ptr);
    while (*ptr && *ptr != ',') ptr++;
    if (*ptr == ',') ptr++;
    target[1] = atoi(ptr);
    
    bool result = solution(ghosts, ghostCount, target);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^n)

Each of n+1 entities (player + ghosts) has 4 movement choices per turn

✓ Linear Growth

Space Complexity

O(4^n)

BFS queue stores exponential number of game states

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

945 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler