The Maze

The Maze

What is this problem about?

The "The Maze" problem is a classic graph traversal challenge set in a 2D grid environment. You are given a maze represented by a matrix of 0s (empty spaces) and 1s (walls). You start at a specific coordinate with a ball that can roll in any of the four cardinal directions (north, south, east, west). However, there's a unique mechanic: once the ball starts rolling, it does not stop until it hits a wall or the boundary of the maze. Your goal is to determine if the ball can eventually reach a designated destination coordinate.

Why is this asked in interviews?

This the Maze interview question is a staple at companies like Uber, Square, and Meta because it tests a candidate's ability to adapt standard pathfinding algorithms (like BFS or DFS) to non-standard movement rules. While a typical maze problem allows you to stop at any cell, this version requires you to think in terms of "stopping points" rather than individual steps. It evaluates your recursion skills (for DFS) or queue management (for BFS) and your ability to handle complex boundary conditions.

Algorithmic pattern used

The problem falls under the Array, Matrix, Breadth-First Search, Depth-First Search interview pattern. You can treat each "stopping point" as a node in a graph. From a given stopping point, you "roll" the ball in all four directions using a loop until it hits a wall. The cell right before the wall becomes a new potential stopping point. You can use BFS to find the shortest path of stopping points or DFS to simply check for reachability. To avoid infinite loops, you must maintain a visited set of the stopping points you've already explored.

Example explanation

Starting at (0,0) in a 5x5 maze where (0,4) is a wall and (4,0) is empty.

1. Roll East: The ball travels (0,1), (0,2), (0,3) and stops at (0,3) because (0,4) is a wall.
2. Roll South: From (0,0), the ball travels (1,0), (2,0), (3,0), (4,0) and stops at (4,0) because it hit the maze boundary.
3. From these new stopping points ((0,3) and (4,0)), you repeat the process, rolling in all four directions. If any of these rolling paths pass through the destination, or more accurately, if the ball stops on the destination, you return true. Note that in some versions of the problem, the ball must stop exactly on the destination to count.

Common mistakes candidates make

In "The Maze coding problem," a common error is marking every cell the ball passes through as visited. This is incorrect because the ball can pass through the same cell multiple times from different directions; only the stopping points need to be tracked to ensure the search terminates. Another mistake is incorrectly handling the "roll" logic, such as stopping the ball inside the wall rather than at the empty cell just before it.

Interview preparation tip

When faced with grid-based movement problems, always clarify the stopping conditions. Is it a step-by-step move or a "slide until you hit something" move? Practice writing a helper function like roll(start_x, start_y, direction) to keep your main BFS/DFS logic clean and readable. This modular approach is highly appreciated by interviewers.