Watch 10 video solutions for Escape a Large Maze, a hard level problem involving Array, Hash Table, Depth-First Search. This walkthrough by Shivam Patel has 3,257 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 != targetsource and target are not blocked.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 | 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 |