How do you solve Escape a Large Maze on LeetCode?

Escape a Large Maze (LeetCode #1036) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: If the source and target are not surrounded by blocked squares, it is possible to reach the target.

What is the brute force solution for Escape a Large Maze?

The brute force approach for Escape a Large Maze is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves exploring all possible paths from the source to the target using a depth-first search (DFS). We will check each move to see if it leads to the target while avoiding blocked squares. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Escape a Large Maze?

Escape a Large Maze uses the following concepts: Array, Hash Table, Depth-First Search, Breadth-First Search. The recommended patterns to study are: Breadth-First Search, Depth-First Search, Hash Set.

What are the interview tips for Escape a Large Maze?

Always consider edge cases, such as when the blocked list is empty. Explain your thought process clearly as you write the code, especially when implementing BFS or DFS. Keep track of visited nodes to avoid infinite loops.

What are common mistakes when solving Escape a Large Maze?

Failing to check for out-of-bounds conditions while exploring neighboring squares. Not considering the case where the number of blocked squares is small, leading to unnecessary complexity.

#1036

Escape a Large Maze

Hard

ArrayHash TableDepth-First SearchBreadth-First SearchBreadth-First SearchDepth-First SearchHash Set

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution leverages the observation that if the source and target are not surrounded by blocked squares, we can reach the target. We can use a breadth-first search (BFS) to explore the area around the source and check if we can reach the target without getting blocked.

⚙️

Algorithm

4 steps

1Step 1: Initialize a queue for BFS starting from the source position.
2Step 2: While the queue is not empty, dequeue the front position and check if it is the target.
3Step 3: If not, check all four possible directions and enqueue valid positions, avoiding blocked squares and out-of-bounds moves.
4Step 4: If the number of steps exceeds a certain limit (e.g., 200), return true since we cannot be blocked indefinitely.

solution.py18 lines

1from collections import deque
2
3def isEscapePossible(blocked, source, target):
4    blocked_set = set(map(tuple, blocked))
5    queue = deque([tuple(source)])
6    directions = [(1,0), (-1,0), (0,1), (0,-1)]
7    steps = 0
8    while queue:
9        x, y = queue.popleft()
10        if (x, y) == tuple(target): return True
11        for dx, dy in directions:
12            nx, ny = x + dx, y + dy
13            if (0 <= nx < 10**6 and 0 <= ny < 10**6 and (nx, ny) not in blocked_set):
14                queue.append((nx, ny))
15                blocked_set.add((nx, ny))
16                steps += 1
17                if steps > 200: return True
18    return False

ℹ

Complexity note: The time complexity is O(n) because we only explore a limited number of steps (up to 200) around the source before concluding that the target is unreachable. The space complexity is O(n) due to the queue used for BFS and the set for blocked squares.

1If the source and target are not surrounded by blocked squares, it is possible to reach the target.
2The maximum number of steps we can explore before concluding that a path is blocked is limited, allowing us to optimize the search.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.