Escape a Large Maze - Solution & Explanation
Problem Statement
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. There is also an array of blocked squares, where each blocked[i] = [xi, yi] represents a blocked square with coordinates (xi, yi).
Each move, we can walk one square north, east, south, or west if the square is not in the array of blocked squares. We are also not allowed to walk outside of the grid.
Return true if and only if it is possible to reach the target square from the source square through a sequence of valid moves.
Example 1:
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. We cannot move north or east because those squares are blocked. We cannot move south or west because we cannot go outside of the grid.
Example 2:
Input: blocked = [], source = [0,0], target = [999999,999999] Output: true Explanation: Because there are no blocked cells, it is possible to reach the target square.
Constraints:
0 <= blocked.length <= 200blocked[i].length == 20 <= xi, yi < 106source.length == target.length == 20 <= sx, sy, tx, ty < 106source != target- It is guaranteed that
sourceandtargetare not blocked.
Approach Overview
Problem Overview: You are given a massive 1,000,000 x 1,000,000 grid with up to 200 blocked cells. Starting from a source cell, determine whether you can reach a target cell without stepping on blocked positions. The grid is too large for full exploration, so the solution relies on understanding how many cells the blocked positions can realistically enclose.
Approach 1: Breadth-First Search (BFS) with Enclosure Limit (O(b2) time, O(b2) space)
A naive BFS across the entire grid is impossible because the search space can reach 10^12 cells. The key insight is that the number of blocked cells (b ≤ 200) limits the maximum area they can surround. If blocked cells form a closed boundary, the largest enclosed region they can create is roughly b * (b - 1) / 2. Run a Breadth-First Search from the source while tracking visited cells using a hash table. If BFS reaches the target, return true immediately. If the search expands beyond the theoretical enclosure limit, the source is not trapped, so escape is possible.
To fully guarantee reachability, repeat the same bounded BFS from the target toward the source. This double check ensures neither endpoint is trapped by blocked cells. The algorithm only explores a few tens of thousands of cells at most, making it practical even with the huge grid size. Coordinates are generated by moving in four directions and skipping blocked or visited cells stored in hash sets.
Alternative: Depth-First Search with the Same Boundary Logic (O(b2) time, O(b2) space)
A Depth-First Search can replace BFS while using the same enclosure limit idea. DFS recursively explores neighbors and stops once the visited count exceeds the maximum possible enclosed area. Functionally the behavior is identical: if exploration escapes the theoretical boundary, the starting position cannot be trapped. BFS is generally preferred because it avoids deep recursion and handles frontier expansion more predictably in large grids.
Recommended for interviews: The bounded BFS approach is the expected solution. Interviewers want to see recognition that the grid size is a red herring and that the true constraint is the number of blocked cells. Explaining the enclosure limit (b * (b - 1) / 2) shows strong algorithmic reasoning. Implementing BFS with a hash set for blocked and visited coordinates demonstrates solid graph traversal fundamentals.
Approach 1: Approach 1: Breadth-First Search (BFS)
This approach leverages the Breadth-First Search (BFS) algorithm to explore the grid from the source point, while checking if the target can be reached without crossing any blocked squares. The BFS is limited by the number of blocked squares, as these block the path. Given that the blocked array is limited to at most 200, the BFS is bounded by a reasonable area since it cannot be contained by more than a certain number of blocked squares.
The BFS algorithm is implemented by initializing a queue with the source coordinates and exploring all possible moves while maintaining a visited grid to avoid revisiting. When a node reaches the target, it returns true. The search is also bound by the amount of blocked squares since they can enclose the start or the target.
Complexity
Time Complexity: O(B^2), where B is the number of blocked cells. This is because if the blocked cells do not enclose the source or the target, the BFS will explore the number of free cells which is squared by nature of exploration.
Space Complexity: O(B^2), similar to the time complexity due to tracking visited nodes.
Approach 2: DFS
The problem can be interpreted as determining whether it is possible to move from a source point to a target point in a 10^6 times 10^6 grid, given a small number of blocked points.
Since the number of blocked points is small, the maximum area that can be blocked is no more than |blocked|^2 / 2. Therefore, we can perform a depth-first search (DFS) starting from both the source and the target points. The search continues until either the target point is reached or the number of visited points exceeds |blocked|^2 / 2. If either condition is satisfied, return true. Otherwise, return false.
Time complexity is O(m), and space complexity is O(m), where m is the size of the blocked region. In this problem, m leq |blocked|^2 / 2 = 200^2 / 2 = 20000.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Breadth-First Search (BFS) | Time Complexity: O(B^2), where B is the number of blocked cells. This is because if the blocked cells do not enclose the source or the target, the BFS will explore the number of free cells which is squared by nature of exploration. Space Complexity: O(B^2), similar to the time complexity due to tracking visited nodes. |
| DFS | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive BFS Over Entire Grid | O(10^12) | O(10^12) | Theoretical baseline; infeasible due to huge grid size |
| Bounded BFS with Enclosure Limit | O(b^2) | O(b^2) | Optimal solution when blocked cells are small (b ≤ 200) |
| DFS with Boundary Limit | O(b^2) | O(b^2) | Alternative traversal if recursion or stack-based exploration is preferred |
Video Solution
Leetcode 1036(Hard) Escape a Large Maze: Simple C++ Solution • Shivam Patel • 3,376 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Escape a Large Maze easy or hard?
Escape a Large Maze Python/Java solution
How to solve Escape a Large Maze in O(b^2)?
What is the best approach for Escape a Large Maze?
Is Escape a Large Maze asked at Google/Amazon/Meta?
What data structure is used in Escape a Large Maze?
What is the time complexity of Escape a Large Maze?
Ready to solve this problem?
Practice Escape a Large Maze with our built-in code editor and test cases.
Practice on FleetCode