Skip to main content
Talentd

The Maze - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDepth-First SearchBreadth-First SearchMatrix6 min readAsked at: Amazon, Microsoft, Apple +10
Practice this problem

Problem Statement

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 = [startrow, startcol] and destination = [destinationrow, destinationcol], 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 <= startrow, destinationrow < m
  • 0 <= startcol, destinationcol < 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.

Approach Overview

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.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Depth-First Search with Rolling SimulationO(m*n)O(m*n)Good for recursive exploration when you want simple implementation and clear state transitions.
Breadth-First Search with QueueO(m*n)O(m*n)Preferred for iterative solutions or when extending to shortest-path variations of the maze problem.

Video Solution

the maze leetcode | August Leetcode challenge | python solution | the maze leetcode python solution • thecodingworld • 10,205 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice The Maze with our built-in code editor and test cases.

Practice on FleetCode
Previous

The Maze II

Next

The Maze III