Escape a Large Maze

Escape a Large Maze

What is this problem about?

The Escape a Large Maze interview question places you on a massive grid, typically 1,000,000 by 1,000,000. You are given a starting point, a target destination, and a list of blocked coordinates. Your task is to determine if it is possible to travel from the source to the target without hitting any blocks. Because the grid is astronomically large, you cannot use a standard grid-based traversal without being extremely clever about your stopping conditions.

Why is this asked in interviews?

Companies like UiPath and Amazon use the Escape a Large Maze coding problem to test a candidate's ability to handle scale. It challenges you to move beyond simple Breadth-First Search (BFS) and think about boundary conditions. The key insight is realizing that if you can move far enough away from the starting point without being enclosed by blocks, you are likely "free." It tests geometric intuition and the ability to optimize memory usage in large-scale environments.

Algorithmic pattern used

The primary Graph interview pattern used here is a Bounded BFS or DFS. Since the number of blocked cells is relatively small (e.g., up to 200), the maximum area they can enclose is limited. Instead of searching the whole grid, you perform a search from the source and another from the target. If the search reaches a certain number of visited nodes (related to the maximum area a set of blocks can enclose) or reaches the other point, you conclude that an escape is possible.

Example explanation

Imagine a 1 million x 1 million grid. There are only 3 blocked cells: (0, 1), (1, 1), (1, 0). These blocks trap the source point (0, 0) in a tiny corner. If your target is (5, 5), a BFS starting at (0, 0) will quickly run out of adjacent cells to visit and conclude it's trapped. However, if the blocks were scattered, the BFS would reach a threshold (say, 20,000 nodes) indicating it's no longer "trapped" in a small pocket.

Common mistakes candidates make

• Memory Overflow: Trying to create a full 2D array for a 10^6 x 10^6 grid.
• Ignoring the Target: Only checking if the source is trapped, forgetting that the target could also be enclosed by blocks.
• Incorrect Threshold: Using a threshold that is too small to account for the maximum possible enclosed area (which is roughly B*(B-1)/2 for B blocks).

Interview preparation tip

When dealing with "infinite" or "extremely large" grids, always look for constraints on the number of obstacles. This usually hints that the solution depends on the obstacles' geometry rather than the grid's dimensions.