MediumArrayDepth-First SearchBreadth-First SearchGraphHeap (Priority Queue)MatrixShortest Path

The Maze II

1 approach, code in every language

A ball is placed in a maze given as a grid `maze`, where `0` marks an empty cell and `1` marks a wall. When the ball starts rolling in a chosen direction, it keeps moving until it collides with a wall (or the maze border) and only then can it pick a new direction.

Given the ball's `start` position and a `destination` cell, return the shortest distance the ball travels to stop exactly at the destination, where distance counts the number of empty cells passed through (excluding the starting cell but including the cell it stops on).

If the ball can never come to rest on the destination cell, return `-1`.

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

One shortest route rolls left, down, left, down and stops on the destination after crossing 12 empty cells in total.

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

Every roll passes over [3,2] without ever stopping on it, so the ball cannot rest at that cell and the answer is -1.

Constraints

m == maze.length
n == maze[i].length
1 <= m, n <= 100
maze[i][j] is 0 or 1.
start.length == 2 and destination.length == 2
0 <= start[0], destination[0] < m
0 <= start[1], destination[1] < n
Both the ball and the destination sit on empty cells and are not at the same position.
The maze contains at least 2 empty cells.

Dijkstra over Stopping Positions

Treat each stopping cell as a graph node and each full roll as a weighted edge; run Dijkstra with a min-heap on rolled distance.

Loading animation…

Intuition

The ball does not move one cell at a time, it slides until a wall stops it, so the graph's nodes are the stopping positions and the edges are complete rolls whose weight is the number of cells crossed. Those weights are additive and non-negative, so Dijkstra over stopping positions yields the minimum total distance to stop at each cell. A min-heap always settles the closest reachable stop first, so the first time the destination is popped we already have its shortest stopping distance. If the destination is never settled, the ball can never rest there and the answer is -1. This is exactly single-source shortest path where generating a neighbor means rolling until a wall.

Algorithm walkthrough

1Keep a 2D dist grid of shortest rolling distances, set the start cell to 0, and push (0, startRow, startCol) onto a min-heap.
2Pop the cell with the smallest rolled distance; if it is the destination, return that distance.
3Skip stale entries whose stored distance is smaller than the popped value.
4For each of the four directions, roll the ball cell by cell until the next cell is a wall or out of bounds, counting the empty cells crossed.
5If reaching that stopping cell via the current path is shorter, update its distance and push the new stopping state.
6When the heap empties without settling the destination, return -1.

Implementation

import heapq
from typing import List


class Solution:
    def shortestDistance(
        self, maze: List[List[int]], start: List[int], destination: List[int]
    ) -> int:
        m, n = len(maze), len(maze[0])
        dist = [[float("inf")] * n for _ in range(m)]
        dr, dc = destination
        dist[start[0]][start[1]] = 0
        heap = [(0, start[0], start[1])]
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        while heap:
            d, r, c = heapq.heappop(heap)
            if r == dr and c == dc:
                return d
            if d > dist[r][c]:
                continue
            for dx, dy in dirs:
                nr, nc, steps = r, c, 0
                while (
                    0 <= nr + dx < m
                    and 0 <= nc + dy < n
                    and maze[nr + dx][nc + dy] == 0
                ):
                    nr += dx
                    nc += dy
                    steps += 1
                if d + steps < dist[nr][nc]:
                    dist[nr][nc] = d + steps
                    heapq.heappush(heap, (d + steps, nr, nc))

        return -1

Time

O(m * n * (m + n) * log(m * n))

Space

O(m * n)

Nodes are stopping positions rather than individual cells; each roll scans up to O(m + n) cells and there are O(m * n) heap operations.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free