The Maze II - Solution & Explanation

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.