LeetCode 505 - The Maze II

This problem presents a maze represented as a 2D grid of size m x n where each cell is either an empty space (0) or a wall (1). A ball starts at a given position and can roll up, down, left, or right.

leetcodemediumarraydepth-first-searchbreadth-first-searchgraph-theoryheap-(priority-queue)matrixshortest-path

LeetCode Problem 505

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Graph Theory, Heap (Priority Queue), Matrix, Shortest Path

Solution

Problem Understanding

This problem presents a maze represented as a 2D grid of size m x n where each cell is either an empty space (0) or a wall (1). A ball starts at a given position and can roll up, down, left, or right. Crucially, the ball will keep rolling in a chosen direction until it hits a wall, so it cannot stop midway on an empty space. The task is to compute the shortest distance the ball must travel to stop exactly at the destination. The distance is measured as the number of empty spaces the ball traverses, excluding the start cell and including the destination cell. If the ball cannot reach the destination or cannot stop there, the function should return -1.

The inputs are guaranteed to be within the following constraints: 1 <= m, n <= 100, ensuring the grid is reasonably small for graph traversal techniques. Both the start and destination are guaranteed to be empty spaces and not coinciding. The maze is bounded by walls, so we never need to check for out-of-bound positions explicitly beyond the grid edges.

Important edge cases include situations where the destination lies along a corridor but cannot be reached as a stopping point, mazes where multiple rolling paths exist, and cases where the start is adjacent to walls limiting initial movement.

Approaches

The most straightforward approach is to attempt brute-force DFS. In this approach, we recursively explore every possible rolling path from the start to the destination. For each cell, we consider rolling in all four directions until hitting a wall, and then continue recursively. While this guarantees that all paths are explored and the correct minimum distance can be found, it is computationally expensive because it may revisit the same positions multiple times with different path lengths, leading to exponential time complexity in the worst case.

The key insight for an optimal solution is that this problem is equivalent to finding the shortest path in a weighted graph, where each node is a stop position and edges represent rolling distances. Because distances are always non-negative, Dijkstra’s algorithm is ideal. We maintain a priority queue where the ball explores the closest unvisited stopping point next, updating distances only if a shorter path is found. This ensures we compute the minimum distance efficiently without redundant exploration.

Approach Time Complexity Space Complexity Notes
Brute Force DFS O(4^(m*n)) O(m*n) Explore all paths recursively; extremely slow due to revisiting nodes.
Optimal Dijkstra O(m_n_log(m*n)) O(m*n) Uses a min-heap to explore shortest paths first; avoids unnecessary revisits.

Algorithm Walkthrough

  1. Initialize a distance matrix of size m x n where each entry represents the shortest known distance to reach that cell. Set all values to infinity except the start, which is 0.
  2. Use a min-heap priority queue to explore positions in order of their current shortest distance. Push the start position and distance 0 into the queue.
  3. While the queue is not empty, pop the cell with the smallest current distance. This ensures we always explore the most promising path first.
  4. For each of the four directions (up, down, left, right), simulate rolling the ball until it hits a wall. Count the number of cells traversed during this roll.
  5. After the ball stops, calculate the new tentative distance to the stopping cell. If this distance is smaller than the previously recorded distance, update the distance matrix and push this cell with the new distance into the queue.
  6. Repeat steps 3-5 until the queue is empty or the destination distance has been finalized.
  7. Return the shortest distance at the destination. If the value is still infinity, return -1 because it means the destination is unreachable.

Why it works: Dijkstra’s algorithm guarantees the shortest path in a graph with non-negative edge weights. Each stop position corresponds to a graph node, and each rolling segment represents a weighted edge. By always exploring the minimal distance first and updating only if shorter paths are found, we avoid redundant computations and correctly compute the shortest distance to the destination.

Python Solution

from typing import List
import heapq

class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        m, n = len(maze), len(maze[0])
        distance = [[float('inf')] * n for _ in range(m)]
        distance[start[0]][start[1]] = 0
        
        heap = [(0, start[0], start[1])]  # (distance, row, col)
        directions = [(0,1), (1,0), (0,-1), (-1,0)]
        
        while heap:
            dist, x, y = heapq.heappop(heap)
            if [x, y] == destination:
                return dist
            if dist > distance[x][y]:
                continue
            for dx, dy in directions:
                nx, ny, steps = x, y, 0
                while 0 <= nx + dx < m and 0 <= ny + dy < n and maze[nx+dx][ny+dy] == 0:
                    nx += dx
                    ny += dy
                    steps += 1
                if dist + steps < distance[nx][ny]:
                    distance[nx][ny] = dist + steps
                    heapq.heappush(heap, (distance[nx][ny], nx, ny))
        
        return -1

The Python code initializes a distance matrix and a min-heap. The while loop ensures that the closest unvisited position is processed next. For each direction, the ball rolls until a wall is encountered, and if the new distance improves upon the previously recorded one, it is updated. This ensures Dijkstra’s algorithm is applied correctly.

Go Solution

import (
    "container/heap"
    "math"
)

type Item struct {
    x, y, dist int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(v any) { *pq = append(*pq, v.(Item)) }
func (pq *PriorityQueue) Pop() any {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[:n-1]
    return item
}

func shortestDistance(maze [][]int, start []int, destination []int) int {
    m, n := len(maze), len(maze[0])
    distance := make([][]int, m)
    for i := range distance {
        distance[i] = make([]int, n)
        for j := range distance[i] {
            distance[i][j] = math.MaxInt32
        }
    }
    distance[start[0]][start[1]] = 0
    
    pq := &PriorityQueue{}
    heap.Init(pq)
    heap.Push(pq, Item{start[0], start[1], 0})
    
    dirs := [][]int{{0,1},{1,0},{0,-1},{-1,0}}
    
    for pq.Len() > 0 {
        item := heap.Pop(pq).(Item)
        x, y, dist := item.x, item.y, item.dist
        if x == destination[0] && y == destination[1] {
            return dist
        }
        if dist > distance[x][y] {
            continue
        }
        for _, d := range dirs {
            nx, ny, steps := x, y, 0
            for nx+d[0] >= 0 && nx+d[0] < m && ny+d[1] >= 0 && ny+d[1] < n && maze[nx+d[0]][ny+d[1]] == 0 {
                nx += d[0]
                ny += d[1]
                steps++
            }
            if dist+steps < distance[nx][ny] {
                distance[nx][ny] = dist + steps
                heap.Push(pq, Item{nx, ny, distance[nx][ny]})
            }
        }
    }
    return -1
}

In Go, a priority queue is implemented using the container/heap interface. Each cell's distance is tracked using a 2D slice. The logic mirrors the Python version, with careful attention to heap operations and integer handling.

Worked Examples

Example 1:

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]

Step 1: Push (0, 0, 4) into the heap.

Step 2: Explore left, roll to (0,1), distance 3. Push (3,0,1).

Step 3: Explore down from (0,1), roll to (2,1), distance 5. Push (5,2,1).

Continue until reaching (4,4) with distance 12.

Example 2:

Start [0,4], Destination `[3,2