The Maze - Solution & Explanation

Problem Overview: You are given a maze represented by a 2D grid where 0 means empty space and 1 means wall. A ball starts at a given position and rolls continuously in one direction until it hits a wall. The task is to determine whether the ball can stop exactly at the destination cell.

The tricky part is the movement rule. The ball does not move one cell at a time. It keeps rolling until it hits a wall, then stops at the last valid position. That means a typical grid traversal must simulate this rolling behavior before exploring the next state.

Approach 1: Depth-First Search Simulation (O(m*n))

Use depth-first search to explore the maze while simulating the ball's rolling motion. From the current position, try four directions (up, down, left, right). For each direction, repeatedly move the ball until the next cell would be a wall or boundary. The ball stops at the last valid position. If that position has not been visited, recursively continue the DFS from there.

A visited matrix prevents revisiting the same stopping points, which avoids infinite loops. The key insight is that only stopping positions matter, not every intermediate cell the ball passes through. The traversal continues until either the destination is reached or all reachable stopping positions are explored. Time complexity is O(m*n) since each cell can be processed once as a stopping point, and space complexity is O(m*n) for recursion stack and visited tracking.

Approach 2: Breadth-First Search (O(m*n))

This approach uses breadth-first search with a queue instead of recursion. Start by pushing the starting position into the queue. For each position popped from the queue, roll the ball in all four directions until it hits a wall. Each stopping cell becomes a new node in the BFS traversal.

Mark each stopping position as visited before adding it to the queue. This ensures every reachable stop is processed once. BFS explores the maze layer by layer and works naturally for shortest-path style exploration, although this problem only asks for reachability. Time complexity remains O(m*n) and space complexity is O(m*n) due to the queue and visited matrix.

Both approaches operate directly on the matrix grid and rely on simulating the rolling mechanic correctly. The main implementation detail is the inner loop that keeps moving the ball until a wall is encountered.

Recommended for interviews: Either DFS or BFS is acceptable and interviewers expect you to recognize this as a graph traversal on a grid with modified movement rules. Starting with the DFS version shows you understand state exploration, while the BFS version demonstrates clean iterative traversal. Correctly implementing the rolling simulation and visited tracking is usually the key evaluation point.