The Maze III - Solution & Explanation

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.