The Maze II

Medium
942.

The Maze II

The Maze II is a medium coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google and Meta interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} maze
 * @param {number[]} start
 * @param {number[]} destination
 * @return {number}
 */
var shortestDistance = function(maze, start, destination) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

The Maze II — Solution in Python, Java & C++

The Maze II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

The Maze II is a medium coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google and Meta interviews.

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.

Hints for The Maze II

  1. Hint 1

    The ball's stopping places are the nodes; one roll is one edge.

  2. Hint 2

    That edge's weight is the number of cells rolled, which varies — so this is not plain breadth-first search.

  3. Hint 3

    Dijkstra's algorithm over stopping places gives the shortest total distance.

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

  1. Set every distance to infinity except the start, which is 0.
  2. Repeatedly take the unfinished cell with the smallest distance.
  3. For each of the four directions, roll until the next cell would be a wall or off the grid, counting steps.
  4. 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

Java

public static int shortestDistance(int[][] maze, int[] start, int[] destination) {
    final int BIG = 1000000000;
    int m = maze.length, n = maze[0].length;
    int cells = m * n;
    int[] dist = new int[cells];
    boolean[] done = new boolean[cells];
    Arrays.fill(dist, BIG);
    int[] dr = { 1, -1, 0, 0 };
    int[] dc = { 0, 0, 1, -1 };
    dist[start[0] * n + start[1]] = 0;
    for (int it = 0; it < cells; it++) {
        int u = -1, best = BIG;
        for (int i = 0; i < cells; i++) {
            if (!done[i] && dist[i] < best) { best = dist[i]; u = i; }
        }
        if (u < 0) break;
        done[u] = true;
        int r = u / n, c = u % n;
        for (int d = 0; d < 4; d++) {
            int 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++;
            }
            int v = nr * n + nc;
            if (dist[u] + steps < dist[v]) dist[v] = dist[u] + steps;
        }
    }
    int t = destination[0] * n + destination[1];
    return dist[t] >= BIG ? -1 : dist[t];
}

C++

int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
    const int BIG = 1000000000;
    int m = (int) maze.size(), n = (int) maze[0].size();
    int cells = m * n;
    vector<int> dist(cells, BIG);
    vector<char> done(cells, 0);
    int dr[4] = { 1, -1, 0, 0 };
    int dc[4] = { 0, 0, 1, -1 };
    dist[start[0] * n + start[1]] = 0;
    for (int it = 0; it < cells; it++) {
        int u = -1, best = BIG;
        for (int i = 0; i < cells; i++) {
            if (!done[i] && dist[i] < best) { best = dist[i]; u = i; }
        }
        if (u < 0) break;
        done[u] = 1;
        int r = u / n, c = u % n;
        for (int d = 0; d < 4; d++) {
            int 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++;
            }
            int v = nr * n + nc;
            if (dist[u] + steps < dist[v]) dist[v] = dist[u] + steps;
        }
    }
    int t = destination[0] * n + destination[1];
    return dist[t] >= BIG ? -1 : dist[t];
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal