Is The Maze easy or hard?

The Maze is considered a Medium difficulty problem. The BFS/DFS traversal itself is straightforward, but many candidates initially struggle with the rolling movement rule where the ball continues moving until hitting a wall rather than stepping one cell at a time.

The Maze Python/Java solution

Python and Java implementations typically use BFS with a queue or DFS with recursion. Both simulate rolling in four directions using loops that continue until a wall or boundary appears, then process the final stopping cell. The overall complexity remains O(m*n).

How to solve The Maze in O(m*n)?

Model the maze as a graph where nodes represent positions where the ball can stop. From each node, roll the ball in four directions until a wall is reached, then enqueue or recurse on that stopping cell. Using BFS or DFS with a visited matrix ensures each position is processed once, giving O(m*n) time complexity.

What is the best approach for The Maze?

The most reliable approach is graph traversal using Breadth-First Search (BFS) or Depth-First Search (DFS). Each step simulates rolling the ball in one direction until it hits a wall, then treats the stopping position as a node in the search. With a visited matrix to avoid revisiting stops, the algorithm runs in O(m*n) time.

Is The Maze asked at Google/Amazon/Meta?

Maze-style traversal problems frequently appear in interviews at companies like Google, Amazon, and Meta because they test grid traversal, BFS/DFS understanding, and state simulation. Variants such as Maze II and Maze III are also common follow-up questions.

What data structure is used in The Maze?

The solution uses a queue for BFS or recursion stack for DFS along with a visited matrix to track explored stopping positions. The maze itself is a 2D matrix, and traversal simulates rolling movement in four directions until a wall is reached.

What is the time complexity of The Maze?

The time complexity is O(m*n), where m and n are the maze dimensions. Each cell can become a stopping position at most once, and from each stop the algorithm explores four rolling directions. Space complexity is also O(m*n) for the visited matrix and queue or recursion stack.

Description Solution Video 12:26

490. The Maze

Medium60.4% acceptance13 companiesPremium elsewhere, free here

There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the m x n maze, the ball's start position and the destination, where start = [start_row, start_col] and destination = [destination_row, destination_col], return true if the ball can stop at the destination, otherwise return false.

You may assume that the borders of the maze are all walls (see examples).

Example 1:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

Example 2:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
Output: false
Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.

Example 3:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
Output: false

Constraints:

m == maze.length
n == maze[i].length
1 <= m, n <= 100
maze[i][j] is 0 or 1.
start.length == 2
destination.length == 2
0 <= start_row, destination_row < m
0 <= start_col, destination_col < n
Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
The maze contains at least 2 empty spaces.