What is the time complexity of Escape The Ghosts?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Escape The Ghosts?

This problem uses Array, Math. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Escape The Ghosts?

Insight 1: The Manhattan distance (sum of absolute differences of coordinates) is the shortest distance between two points in this grid. Insight 2: To escape, you must reach the target before any ghost. This implies your Manhattan distance to the target must be strictly less than any ghost's Manhattan distance to the target.

Which companies ask LeetCode 789. Escape The Ghosts in interviews?

This problem is frequently asked at Wix.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Escape The Ghosts - LeetCode 789 Solution

Escape The Ghosts - Complete Solution Guide

Escape The Ghosts is LeetCode problem 789, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 get to. 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. All inputs are integral coordinates . Each turn, you and all the ghosts may independently choose to either move 1 unit in

Detailed Explanation

The problem presents a scenario where you are playing a simplified Pac-Man game on an infinite 2D grid. You start at (0, 0) and need to reach a target location (x_target, y_target). There are multiple ghosts with their own starting positions. Both you and the ghosts can move one unit in any of the four cardinal directions (north, east, south, west) or stay still in each turn, simultaneously. The goal is to determine if you can reach the target *before* any ghost reaches you. If a ghost and you arrive at the same square at the same time, it's considered a failure to escape.

Solution Approach

The solution calculates the Manhattan distance from the starting point (0,0) to the target for the player and the Manhattan distance from each ghost's starting position to the target. It then compares the player's distance to each ghost's distance. If any ghost can reach the target in a distance less than or equal to the player's distance, it returns `false` (escape impossible). Otherwise, it returns `true` (escape possible).

Step-by-Step Algorithm

Step 1: Calculate the Manhattan distance from the player's starting point (0, 0) to the target (target[0], target[1]). This distance is `abs(target[0]) + abs(target[1])`.
Step 2: Iterate through the list of ghosts.
Step 3: For each ghost, calculate the Manhattan distance from its starting position (ghost[0], ghost[1]) to the target (target[0], target[1]). This distance is `abs(ghost[0] - target[0]) + abs(ghost[1] - target[1])`.
Step 4: Compare the ghost's distance to the player's distance. If the ghost's distance is less than or equal to the player's distance, it means the ghost can reach the target at the same time or sooner than the player, making escape impossible. Return `false` in this case.
Step 5: If the loop completes without finding any ghost that can reach the target as fast or faster than the player, it means the player can escape. Return `true`.

Key Insights

Insight 1: The Manhattan distance (sum of absolute differences of coordinates) is the shortest distance between two points in this grid.
Insight 2: To escape, you must reach the target before any ghost. This implies your Manhattan distance to the target must be strictly less than any ghost's Manhattan distance to the target.
Insight 3: If at least one ghost can reach the target in the same number of steps or fewer than you, there's no way to escape, regardless of the ghost's movements.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Math.

Companies

Asked at: Wix.

Escape The Ghosts | LeetCode 789

Medium

Array Math

Time: O(n)Space: O(1)

Solution Code

Available in:

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

        for (int[] ghost : ghosts) {
            int ghost_dist = Math.abs(ghost[0] - target[0]) + Math.abs(ghost[1] - target[1]);
            if (ghost_dist <= player_dist) {
                return false;
            }
        }

        return true;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 789: Escape The Ghosts - Detailed explanation and solution approaches.

Topics

Array Math

Companies

Wix

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:789

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Calculate the Manhattan distance from the player's starting point (0, 0) to the target (target[0], target[1]). This distance is `abs(target[0]) + abs(target[1])`.
2
Step 2: Iterate through the list of ghosts.
3
Step 3: For each ghost, calculate the Manhattan distance from its starting position (ghost[0], ghost[1]) to the target (target[0], target[1]). This distance is `abs(ghost[0] - target[0]) + abs(ghost[1] - target[1])`.
4
Step 4: Compare the ghost's distance to the player's distance. If the ghost's distance is less than or equal to the player's distance, it means the ghost can reach the target at the same time or sooner than the player, making escape impossible. Return `false` in this case.
5
Step 5: If the loop completes without finding any ghost that can reach the target as fast or faster than the player, it means the player can escape. Return `true`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is linear because the dominant operation is the loop that iterates through the ghosts array. The space complexity is constant because only a few integer variables are used to store distances and for loop control, and these do not depend on the input size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Sorting Ghosts by Distance

Sort the ghosts based on their Manhattan distance to the target. The first ghost in the sorted list would be the one that can reach the target the fastest. You would still need to calculate your distance to the target and compare it with the closest ghost.

Time: O(n log n) due to the sorting operation.Space: O(1) or O(n) depending on the sorting algorithm used (in-place or not).

Trade-offs: This approach is less efficient than the main solution because of the sorting step. It might be useful if you need to repeatedly query the closest ghost after the initial calculation.

✨

Key Insights

1Insight 1: The Manhattan distance (sum of absolute differences of coordinates) is the shortest distance between two points in this grid.
2Insight 2: To escape, you must reach the target before any ghost. This implies your Manhattan distance to the target must be strictly less than any ghost's Manhattan distance to the target.
3Insight 3: If at least one ghost can reach the target in the same number of steps or fewer than you, there's no way to escape, regardless of the ghost's movements.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: A ghost starts at the same location as the target. In this case, the ghost's distance to the target is 0. The solution correctly handles this because the player's distance to the target must be strictly less than the ghost's, so if the ghost is already at the target, you cannot escape.
Edge case 2: Multiple ghosts are located at the same position. The solution iterates through all ghosts, and each ghost's distance is calculated and compared individually, so this is handled correctly.
Edge case 3: The target is at the origin (0,0). The algorithm handles this case correctly. The player's distance is 0. If any ghost is also at the origin, the ghost's distance is also 0, hence you cannot escape, which is the correct outcome.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Using Euclidean distance instead of Manhattan distance. The problem specifies movement in cardinal directions, so Manhattan distance is the appropriate metric.

✗Common mistake 2: Incorrectly comparing distances. Remember that the player's distance must be *strictly less than* the ghost's distance to escape. Failing to check for equality can lead to incorrect results.

✗Common mistake 3: Not considering the initial positions of ghosts and assuming they immediately move towards the player instead of target.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Pathfinding in a grid-based environment, like a robot navigating a warehouse or a vehicle navigating a city grid, where avoiding obstacles (ghosts) is crucial to reaching a destination.

🏦Real-world scenario 2: Resource allocation. Suppose you need to allocate resources to a location, but there are competing agents (ghosts) also trying to reach the same location. You need to determine if it's possible to allocate resources before the other agents can reach the location.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 9, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Escape The Ghosts"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether math techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?