The Maze II
Medium · Heap / Priority Queue · Explanation and code example
Dijkstra's Algorithm and Priority Queue
How it works
Using a priority queue (min-heap) optimizes Dijkstra's algorithm by efficiently extracting the position with the minimum distance. Instead of scanning the entire matrix, we simply pop from the heap.
When we pop a position from the heap, if its distance is already worse than what we have recorded, we skip it (this handles duplicate entries). Otherwise, we explore all four directions and add newly discovered shorter paths to the heap.
Steps
- Initialize a distance matrix with infinity. Set start distance to
0. - Add the start position to a min-heap, ordered by distance.
- While the heap is not empty:
- Pop the position with minimum distance.
- If its distance exceeds the recorded distance, skip it.
- For each direction, roll the ball and count the distance.
- If the new distance is shorter, update the distance matrix and push the new position to the heap.
- Return the distance at the destination, or
-1if unreachable.
Complexity
- Time complexity:
O(mn × log(mn)) - Space complexity:
O(m × n)
Where
mandnare the number of rows and columns inmaze.
Things to watch for
Stopping BFS on First Arrival at Destination
Unlike standard BFS where the first path to a node is the shortest, the ball can reach the same position via paths of different lengths due to variable rolling distances. You must continue exploring until all shorter paths are exhausted. The correct approach is to only finalize a distance when extracted from a priority queue or when no shorter path exists.
Counting Distance Incorrectly During Rolling
The ball rolls through multiple cells before stopping, and each cell traversed counts as one unit of distance. A common error is counting only the stopping position or miscounting the cells rolled. Increment the counter inside the while loop as the ball moves, not after it stops.
Forgetting to Step Back After Hitting a Wall
The rolling loop continues until the ball hits a wall or boundary, meaning the final position is invalid. You must subtract the direction vector once to get the actual stopping position. Forgetting this step causes the ball to be placed inside walls or outside the maze.
Python code example
from typing import List
import heapq
class Solution:
def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
distance = [[float('inf')] * len(maze[0]) for _ in range(len(maze))]
distance[start[0]][start[1]] = 0
self.dijkstra(maze, start, distance)
return -1 if distance[destination[0]][destination[1]] == float('inf') else distance[destination[0]][destination[1]]
def dijkstra(self, maze: List[List[int]], start: List[int], distance: List[List[int]]) -> None:
dirs = [[0, 1], [0, -1], [-1, 0], [1, 0]]
queue = []
heapq.heappush(queue, (0, start[0], start[1])) # (distance, x, y)
while queue:
dist, sx, sy = heapq.heappop(queue)
if distance[sx][sy] < dist:
continue
for dx, dy in dirs:
x, y = sx + dx, sy + dy
count = 0
while 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0:
x += dx
y += dy
count += 1
if distance[sx][sy] + count < distance[x - dx][y - dy]:
distance[x - dx][y - dy] = distance[sx][sy] + count
heapq.heappush(queue, (distance[x - dx][y - dy], x - dx, y - dy))
C++ code example
class Solution {
public:
int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
int m = maze.size();
int n = maze[0].size();
vector<vector<int>> distance(m, vector<int>(n, INT_MAX));
distance[start[0]][start[1]] = 0;
dijkstra(maze, start, distance);
return distance[destination[0]][destination[1]] == INT_MAX ? -1 : distance[destination[0]][destination[1]];
}
private:
void dijkstra(vector<vector<int>>& maze, vector<int>& start, vector<vector<int>>& distance) {
int m = maze.size();
int n = maze[0].size();
vector<vector<int>> dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
// Min-heap: {distance, x, y}
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
pq.push({0, start[0], start[1]});
while (!pq.empty()) {
vector<int> s = pq.top();
pq.pop();
int dist = s[0], sx = s[1], sy = s[2];
if (distance[sx][sy] < dist)
continue;
for (auto& dir : dirs) {
int x = sx + dir[0];
int y = sy + dir[1];
int count = 0;
while (x >= 0 && y >= 0 && x < m && y < n && maze[x][y] == 0) {
x += dir[0];
y += dir[1];
count++;
}
if (distance[sx][sy] + count < distance[x - dir[0]][y - dir[1]]) {
distance[x - dir[0]][y - dir[1]] = distance[sx][sy] + count;
pq.push({distance[x - dir[0]][y - dir[1]], x - dir[0], y - dir[1]});
}
}
}
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.