← Visualizers
Graphs · Grid BFS on stopping points LeetCode 490

The Maze / visualized

The ball doesn't move one cell at a time: it rolls continuously in a direction until hitting a wall. This means graph vertices are not cells, but stopping points! Rolling over the destination mid-flight does not solve the maze; the ball must come to a complete stop at the destination cell.

Maze Board · Raycasting

idle
INVARIANT The Maze Stopping Invariant: The ball cannot steer mid-roll—it rolls continuously in a chosen direction until hitting a wall. BFS nodes are STOPPING POINTS, not individual cells. Passing through destination while rolling does NOT count: the ball must come to a complete stop at destination!
Press Run to begin.
0 / 0
Speed

Java · running line

wall (1) ball / current stop destination stopping point roll raycast
INTERVIEW SCRIPT

How to Explain The Maze to an Interviewer

1. Graph Modeling on Stopping Points

"The vertices in this BFS graph are NOT the $m \times n$ grid cells. A vertex is specifically a cell where the ball comes to rest against a wall. Edges represent complete continuous rolls."

2. The While Loop Raycast

"From a stopping point, we test 4 directions. In each direction, an inner while loop advances coordinates until hitting a wall: while (valid && maze[nr+dr][nc+dc] == 0) { nr += dr; nc += dc; }"

3. The Destination Stopping Invariant

"A common pitfall is checking if (nr == dest[0] && nc == dest[1]) inside the rolling loop. That is incorrect because the ball cannot stop on command; it only checks for destination at the final resting cell."

4. Complexity Guarantee

"There are at most $m \cdot n$ stopping points. From each stopping point, raycasting rolls at most $O(m + n)$ steps. Overall time complexity is $O(m \cdot n \cdot (m + n))$."

O(m·n·(m+n)) time, O(m·n) space  ·  BFS explores stopping points where ball hits walls.