Skip to main content
Talentd

The Maze III - Solution & Explanation

HardPremiumFree on FleetCodeArrayStringDepth-First SearchBreadth-First Search8 min readAsked at: Google
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 (must be different from last chosen direction). There is also a hole in this maze. The ball will drop into the hole if it rolls onto the hole.

Given the m x n maze, the ball's position ball and the hole's position hole, where ball = [ballrow, ballcol] and hole = [holerow, holecol], return a string instructions of all the instructions that the ball should follow to drop in the hole with the shortest distance possible. If there are multiple valid instructions, return the lexicographically minimum one. If the ball can't drop in the hole, return "impossible".

If there is a way for the ball to drop in the hole, the answer instructions should contain the characters 'u' (i.e., up), 'd' (i.e., down), 'l' (i.e., left), and 'r' (i.e., right).

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,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"
Explanation: There are two shortest ways for the ball to drop into the hole.
The first way is left -> up -> left, represented by "lul".
The second way is up -> left, represented by 'ul'.
Both ways have shortest distance 6, but the first way is lexicographically smaller because 'l' < 'u'. So the output is "lul".

Example 2:

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]], ball = [4,3], hole = [3,0]
Output: "impossible"
Explanation: The ball cannot reach the hole.

Example 3:

Input: maze = [[0,0,0,0,0,0,0],[0,0,1,0,0,1,0],[0,0,0,0,1,0,0],[0,0,0,0,0,0,1]], ball = [0,4], hole = [3,5]
Output: "dldr"

 

Constraints:

  • m == maze.length
  • n == maze[i].length
  • 1 <= m, n <= 100
  • maze[i][j] is 0 or 1.
  • ball.length == 2
  • hole.length == 2
  • 0 <= ballrow, holerow <= m
  • 0 <= ballcol, holecol <= n
  • Both the ball and the hole 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 a direction until it hits a wall. The goal is to find the shortest distance for the ball to fall into a hole. If multiple shortest paths exist, return the lexicographically smallest path string. If the ball cannot reach the hole, return "impossible".

This problem combines grid traversal with weighted shortest path logic. Each roll travels multiple cells until a wall stops the ball, which means standard step-by-step traversal does not apply. The path string also introduces a lexicographical constraint when distances tie.

Approach 1: DFS with Backtracking (Exponential Time)

One direct idea is to simulate all possible rolling paths using Depth-First Search. From the current cell, roll the ball in four directions until it hits a wall or the hole. Track the distance traveled and the path string. Maintain the best result found so far and prune branches where the current distance already exceeds it. Time complexity is exponential in the number of open cells because many paths are explored repeatedly, and space complexity is O(mn) for recursion and visited tracking. This approach demonstrates the mechanics of rolling movement but struggles with performance on large grids.

Approach 2: BFS with Distance Tracking (O(mn * max(m,n)))

You can treat each stopping position as a node and use Breadth-First Search. From every node, roll in four directions until hitting a wall and enqueue the stopping cell. Maintain a distance matrix storing the shortest distance to each cell. However, since each roll may travel multiple steps, edges effectively have different weights. Plain BFS does not always guarantee optimal ordering, so additional checks are required to update distances and paths. Time complexity becomes O(mn * max(m,n)) because each roll scans up to the maze dimension. Space complexity is O(mn).

Approach 3: Dijkstra with Priority Queue (Optimal) (O(mn log(mn)))

The optimal solution models the maze as a weighted graph and applies Dijkstra's algorithm using a priority queue. Each state contains (distance, path, row, col). Always expand the node with the smallest distance; if distances tie, compare path strings lexicographically. For each direction, simulate the rolling process until hitting a wall or the hole, count the steps taken, and push the resulting cell into the heap. Maintain a visited or distance map to avoid processing worse states. The time complexity is O(mn log(mn)) due to heap operations over grid cells, and space complexity is O(mn). This method guarantees both the shortest distance and the lexicographically smallest path.

Recommended for interviews: Dijkstra with a priority queue is the expected solution. Interviewers want to see that you recognize the rolling movement creates weighted edges, making BFS insufficient. Implementing the algorithm cleanly on a matrix grid while tracking lexicographical paths demonstrates strong shortest path problem-solving skills.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with BacktrackingExponentialO(mn)Conceptual exploration or small mazes where performance is not critical
BFS with Distance UpdatesO(mn * max(m,n))O(mn)Intermediate approach when modeling grid traversal but before recognizing weighted edges
Dijkstra with Priority QueueO(mn log(mn))O(mn)General case. Handles weighted rolling distances and lexicographic tie-breaking correctly

Video Solution

Leetcode 499. The Maze III • Algorithms for Big Bucks • 1,166 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is The Maze III easy or hard?
The Maze III is classified as a Hard problem because it combines multiple concepts: rolling movement simulation, lexicographical path comparison, and Dijkstra's shortest path algorithm on a grid. Handling both distance optimization and path ordering makes the implementation tricky.
The Maze III Python/Java solution
Implement Dijkstra's algorithm using a min-heap from the standard library. Push tuples containing distance, path string, and coordinates. Simulate rolling in each direction until hitting a wall, update distance and path, and push the new state into the heap if it improves the current best result.
How to solve The Maze III in O(mn log mn)?
Model each stopping position of the rolling ball as a graph node and apply Dijkstra's algorithm. Use a priority queue storing (distance, path, row, col). For every expansion, roll the ball in four directions until hitting a wall or the hole, compute the travel distance, and push the result into the heap if it improves the best known state.
What is the best approach for The Maze III?
The most effective solution uses Dijkstra's algorithm with a priority queue. Each state stores distance, path string, and position. The heap ensures the smallest distance is processed first, and lexicographical comparison of path strings resolves ties. This guarantees the shortest path while meeting the lexicographic requirement.
Is The Maze III asked at Google/Amazon/Meta?
Maze-style graph traversal problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants such as The Maze I, II, and III test understanding of grid graphs, rolling movement constraints, and shortest path algorithms like BFS or Dijkstra.
What data structure is used in The Maze III?
The optimal solution relies on a priority queue (min-heap) along with a distance matrix. The priority queue always selects the state with the smallest distance, while the matrix stores the best known distance to each cell in the maze grid.
What is the time complexity of The Maze III?
The optimal Dijkstra-based solution runs in O(mn log(mn)) time where m and n are the maze dimensions. Each cell can be inserted into the priority queue, and heap operations introduce the logarithmic factor. Space complexity is O(mn) for distance tracking and heap storage.

Ready to solve this problem?

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

Practice on FleetCode
Previous

The Maze

Next

The Maze II