Escape a Large Maze
HardPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
A straightforward but impractical approach is to model the entire 10^6 x 10^6 grid as a graph and perform a standard traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS). We would start at the source and explore adjacent cells, keeping track of visited cells to avoid cycles, until we either find the target or exhaust all reachable cells.
Algorithm
- Treat the 10^6 x 10^6 grid as a graph.
- Start a Breadth-First Search (BFS) or Depth-First Search (DFS) from the
sourcecoordinate. - Use a queue (for BFS) or stack (for DFS) to manage coordinates to visit.
- Use a large hash set to keep track of
visitedcoordinates to avoid cycles and redundant computations. - In each step, explore the four neighbors (north, east, south, west).
- If a neighbor is within the grid boundaries, not blocked, and not visited, add it to the queue/stack and the visited set.
- Continue the search until the
targetcoordinate is found (returntrue) or the queue/stack becomes empty (returnfalse).
Walkthrough
This method directly translates the problem into a graph traversal problem without considering the specific constraints. The grid cells are the nodes, and valid moves between adjacent cells are the edges. A standard BFS would guarantee finding the shortest path if one exists, but we only need to determine existence. However, the sheer size of the grid makes this approach infeasible. The number of cells is 10^12, so any algorithm that attempts to visit a significant fraction of the grid or store their visited status will fail due to time and memory constraints.
Complexity
Time
O(N*M) in the worst case, where N and M are the grid dimensions. This is far too slow for the given constraints.
Space
O(N*M), where N and M are the dimensions of the grid (10^6 x 10^6). This is required for the `visited` set and is prohibitively large.
Trade-offs
Pros
Conceptually simple and easy to understand.
Cons
Memory Limit Exceeded: The
visitedset could potentially store up to 10^12 coordinates, which is far beyond the memory capacity of any typical competitive programming environment.Time Limit Exceeded: The search space is enormous. In an open grid, the search would explore a vast number of cells before reaching a distant target, leading to a timeout.
Solutions
Solution
class Solution {private int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};private static final int N = (int)1 e6;private Set<Integer> blocked;public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) { this.blocked = new HashSet<>(); for (int[] b : blocked) { this.blocked.add(b[0] * N + b[1]); } return dfs(source, target, new HashSet<>()) && dfs(target, source, new HashSet<>()); }private boolean dfs(int[] source, int[] target, Set<Integer> seen) { int sx = source[0], sy = source[1]; int tx = target[0], ty = target[1]; if (sx < 0 || sx >= N || sy < 0 || sy >= N || tx < 0 || tx >= N || ty < 0 || ty >= N || blocked.contains(sx * N + sy) || seen.contains(sx * N + sy)) { return false; } seen.add(sx * N + sy); if (seen.size() > 20000 || (sx == target[0] && sy == target[1])) { return true; } for (int[] dir : dirs) { if (dfs(new int[]{sx + dir[0], sy + dir[1]}, target, seen)) { return true; } } return false; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.