The Maze II — Medium Problem & Solution

A ball rolls through a maze of empty spaces (0) and walls (1).

Difficulty: Medium
Topics: Arrays, Matrix, Breadth-First Search, Graph, Shortest Path
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A ball rolls through a maze of empty spaces (0) and walls (1). When it starts rolling in one of the four directions it does not stop until it hits a wall; only then may it pick a new direction.

Given the ball's start and a destination, return the shortest distance the ball travels to stop at the destination, or -1 if it can never stop there. Distance counts empty cells travelled, not including the starting cell.

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
Explanation: Left, down, left, down covers 12 cells.

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
Explanation: The ball rolls past that cell but never stops on it.

Example 3

Input: maze = [[0,0],[0,0]], start = [0,0], destination = [1,1]
Output: 2

Constraints

m == maze.length
n == maze[i].length
1 <= m, n <= 100
maze[i][j] is 0 or 1
start.length == destination.length == 2
0 <= start[0], destination[0] < m
0 <= start[1], destination[1] < n
Both the ball and the destination sit on an empty cell.
The maze is surrounded by walls in the sense that the ball stops at the border.

How to solve The Maze II

The graph's nodes are the cells the ball can come to rest on, and an edge is one full roll whose weight is its length. Because the weights differ, use Dijkstra's algorithm rather than BFS.

Approach

Set every distance to infinity except the start, which is 0.
Repeatedly take the unfinished cell with the smallest distance.
For each of the four directions, roll until the next cell would be a wall or off the grid, counting steps.
Relax the stopping cell with dist[u] + steps.

Why it works

Plain BFS is wrong here because it counts rolls, not cells: a route of two long rolls would beat a route of three short ones even when it travels further. Dijkstra's algorithm orders by accumulated distance instead, which is what the question asks for. Note the destination only counts if the ball stops there, so rolling through it is not an arrival.

Complexity

Time — O((m · n)² ) with a linear scan, or O(m · n · log(m · n)) with a heap
Space — O(m · n)

Pitfalls

Passing over the destination does not count; the ball must come to rest there.
A roll of length 0 happens when a wall is immediately adjacent; it relaxes nothing new.
Treating every roll as cost 1 answers a different question.

Reference solution

Python

from typing import List
import heapq

def shortestDistance(maze: List[List[int]], start: List[int], destination: List[int]) -> int:
    m, n = len(maze), len(maze[0])
    BIG = float('inf')
    dist = [[BIG] * n for _ in range(m)]
    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 d > dist[r][c]:
            continue
        for di, dj in dirs:
            nr, nc, steps = r, c, 0
            while 0 <= nr + di < m and 0 <= nc + dj < n and maze[nr + di][nc + dj] == 0:
                nr += di
                nc += dj
                steps += 1
            if d + steps < dist[nr][nc]:
                dist[nr][nc] = d + steps
                heapq.heappush(heap, (d + steps, nr, nc))
    best = dist[destination[0]][destination[1]]
    return -1 if best == BIG else best

JavaScript

var shortestDistance = function(maze, start, destination) {
    var BIG = 1000000000;
    var m = maze.length, n = maze[0].length, i;
    var cells = m * n;
    var dist = [], done = [];
    for (i = 0; i < cells; i++) { dist.push(BIG); done.push(false); }
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    dist[start[0] * n + start[1]] = 0;
    for (var it = 0; it < cells; it++) {
        var u = -1, best = BIG;
        for (i = 0; i < cells; i++) {
            if (!done[i] && dist[i] < best) { best = dist[i]; u = i; }
        }
        if (u < 0) break;
        done[u] = true;
        var r = Math.floor(u / n), c = u % n;
        for (var d = 0; d < 4; d++) {
            var nr = r, nc = c, steps = 0;
            while (nr + dr[d] >= 0 && nr + dr[d] < m && nc + dc[d] >= 0 && nc + dc[d] < n
                && maze[nr + dr[d]][nc + dc[d]] === 0) {
                nr += dr[d];
                nc += dc[d];
                steps++;
            }
            var v = nr * n + nc;
            if (dist[u] + steps < dist[v]) dist[v] = dist[u] + steps;
        }
    }
    var t = destination[0] * n + destination[1];
    return dist[t] >= BIG ? -1 : dist[t];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue