How hard is LeetCode 1036. Escape a Large Maze?

LeetCode 1036. Escape a Large Maze is rated Hard on LeetCode.

What is the time complexity of LeetCode 1036. Escape a Large Maze?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1036. Escape a Large Maze?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1036. Escape a Large Maze cover?

LeetCode 1036. Escape a Large Maze is tagged Depth-First Search, Breadth-First Search, Array and Hash Table on LeetCode.

Escape a Large Maze — LeetCode 1036 Python Solution

HardDepth-First SearchBreadth-First SearchArrayHash Table

Problem: #1036
Pattern: Breadth-First Search
Reading time: 4 min
Source: leetcode.com

The problem

There is a 1 million by 1 million grid on an XY-plane, and the coordinates of each grid square are (x, y). We start at the source = [sx, sy] square and want to reach the target = [tx, ty] square.

Example

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false
Explanation: The target square is inaccessible starting from the source square because we cannot move.

Python solution

Python

class Solution:
    def isEscapePossible(
        self, blocked: List[List[int]], source: List[int], target: List[int]
    ) -> bool:
        def dfs(source: List[int], target: List[int], vis: set) -> bool:
            vis.add(tuple(source))
            if len(vis) > m:
                return True
            for a, b in pairwise(dirs):
                x, y = source[0] + a, source[1] + b
                if 0 <= x < n and 0 <= y < n and (x, y) not in s and (x, y) not in vis:
                    if [x, y] == target or dfs([x, y], target, vis):
                        return True
            return False

        s = {(x, y) for x, y in blocked}
        dirs = (-1, 0, 1, 0, -1)
        n = 10**6
        m = len(blocked) ** 2 // 2
        return dfs(source, target, set()) and dfs(target, source, set())

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Breadth-First Search

Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 1036. Escape a Large Maze is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.

The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1036. Escape a Large Maze?: LeetCode 1036. Escape a Large Maze is rated Hard on LeetCode.
What is the time complexity of LeetCode 1036. Escape a Large Maze?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1036. Escape a Large Maze?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1036. Escape a Large Maze cover?: LeetCode 1036. Escape a Large Maze is tagged Depth-First Search, Breadth-First Search, Array and Hash Table on LeetCode.