Skip to main content
Talentd

The Maze II - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDepth-First SearchBreadth-First SearchGraph7 min readAsked at: Amazon, Meta, Uber +2
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 the shortest distance for the ball to stop at the destination. If the ball cannot stop at destination, return -1.

The distance is the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included).

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: 12
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

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: -1
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: -1

 

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 where a ball rolls in one direction until it hits a wall. From a start cell, find the minimum distance the ball must travel to stop exactly at the destination. Unlike typical grid problems, the ball does not stop at every cell—it only stops when it hits a wall, which makes pathfinding slightly different from standard BFS.

Approach 1: BFS with Distance Relaxation (O(mn * max(m,n)) time, O(mn) space)

A naive attempt is to treat the grid like a normal breadth-first search problem. From each stopping point, simulate rolling the ball in four directions until it hits a wall. Track the number of steps traveled during the roll and update the distance for the stopping cell if a shorter path is found. Because edges have different weights (the roll distance varies), the same cell might need to be revisited with a shorter distance. The algorithm maintains a distance matrix and pushes cells back into the queue whenever a shorter path is discovered.

Approach 2: Dijkstra with Priority Queue (O(mn log(mn)) time, O(mn) space)

The optimal solution models the maze as a weighted graph and runs Dijkstra’s algorithm. Each cell is a node, and rolling in a direction forms a weighted edge whose weight equals the number of steps traveled before hitting a wall. Use a min-heap (priority queue) to always process the cell with the smallest known distance. From the current cell, simulate rolling in four directions, compute the travel distance, and relax the distance if the new path is shorter. A distance matrix prevents unnecessary processing. This approach guarantees that once a node is popped from the heap with the minimum distance, its shortest path is finalized.

The grid structure naturally fits a graph shortest-path problem, while the rolling behavior defines the weighted edges. The key insight is that the ball travels multiple cells in one move, so every move has a variable cost rather than a uniform step.

Recommended for interviews: Dijkstra with a priority queue. Interviewers expect you to recognize that BFS alone does not work because the edge weights differ. Showing the BFS attempt demonstrates understanding of grid traversal, but identifying the weighted-graph nature and switching to Dijkstra shows strong algorithmic reasoning.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS with Distance RelaxationO(mn * max(m,n))O(mn)Useful as a conceptual step when exploring the grid and simulating rolling movement
Dijkstra with Priority QueueO(mn log(mn))O(mn)Best for weighted shortest-path problems where movement cost varies

Video Solution

LeetCode 505. The Maze II • Happy Coding • 5,195 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is The Maze II easy or hard?
The Maze II is rated Medium but feels harder if you treat it like a standard BFS grid problem. The challenge comes from recognizing that movement has variable cost because the ball rolls multiple cells at once, which requires a weighted shortest-path algorithm like Dijkstra.
The Maze II Python/Java solution
Most implementations use Dijkstra with a priority queue. Maintain a distance matrix and push states into the heap as (distance, row, col). For each state, simulate rolling in four directions until a wall stops the ball, update distances, and continue until the destination is reached or the heap is empty.
How to solve The Maze II in O(mn log mn)?
Model the maze as a weighted graph and run Dijkstra's algorithm. Use a priority queue to always expand the cell with the smallest current distance. For each direction, simulate rolling until a wall is hit, compute the distance traveled, and update the shortest path if the new distance is smaller.
What is the best approach for The Maze II?
The optimal approach uses Dijkstra's algorithm with a min-heap (priority queue). Each roll in the maze creates a weighted edge equal to the number of cells traveled before hitting a wall. Dijkstra guarantees the shortest distance to every stopping point and runs in O(mn log(mn)) time with O(mn) space.
Is The Maze II asked at Google/Amazon/Meta?
The Maze II is a common grid and graph shortest-path interview question seen in companies like Google, Amazon, and Meta. It tests whether candidates recognize when BFS is insufficient and switch to Dijkstra for weighted path problems.
What data structure is used in The Maze II?
The core data structure is a min-heap priority queue used by Dijkstra's algorithm. The solution also uses a distance matrix to track the shortest known distance to each cell and a grid representation of the maze.
What is the time complexity of The Maze II?
The optimal Dijkstra-based solution runs in O(mn log(mn)) time where m and n are the maze dimensions. Each cell may be processed in the priority queue, and heap operations add the logarithmic factor. Space complexity is O(mn) for the distance matrix and heap.

Ready to solve this problem?

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

Practice on FleetCode
Previous

The Maze

Next

The Maze III