Problem of The Day: The Maze II

Problem Statement

• Note: using Dijkstra’s algorithm

Intuition

The problem requires finding the shortest distance from the starting point to the destination in a maze. The key insight is that the ball keeps rolling in one direction until it hits a wall, making this a variation of the shortest-path problem. Using a priority queue allows us to explore the shortest paths first, similar to Dijkstra’s algorithm.

Approach

1. Initialization:

   • Store the number of rows (ROWS) and columns (COLS) of the maze.
   • Create a distances matrix initialized to infinity (float('inf')) for all cells except the start cell, which is initialized to 0.
   • Define the four possible movement directions as (down, up, right, left).

2. Priority Queue:

   • Use a priority queue (min-heap) to keep track of the cell coordinates and the distance traveled to reach them.

3. Iterative Search:

   • While the priority queue is not empty:
     • Pop the cell with the smallest distance from the queue.
     • For each direction:
       • Roll the ball in that direction until it hits a wall or boundary.
       • Calculate the distance traveled in this direction.
       • If the new distance is shorter than the currently recorded distance for the stopping cell, update it and add the cell to the priority queue.

4. Return Result:

   • After processing all reachable cells, check the distances value for the destination cell.
   • If it is still infinity, return -1 (unreachable); otherwise, return the shortest distance.

Complexity

• Time complexity: \(O(m \cdot n \cdot \log(m \cdot n))\)

  • Each cell can be processed once, and for each cell, we push/pull from the priority queue which takes \(O(\log(m \cdot n))\) operations.

• Space complexity: \(O(m \cdot n)\)

  • We use a distances matrix and a priority queue that can hold up to \(m \cdot n\) elements in the worst case.

Code

class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        ROWS = len(maze)
        COLS = len(maze[0])
        distances = [[float('inf') for _ in range(COLS)] for _ in range(ROWS)]
        distances[start[0]][start[1]] = 0
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        priority_queue = [[start[0], start[1], 0]]
        while priority_queue:
            row, col, distance = heapq.heappop(priority_queue)
            if distances[row][col] < distance:
                continue

            for dx, dy in directions:
                nr, nc = row + dx, col + dy
                curr_distance = 0
                while 0 <= nr < ROWS and 0 <= nc < COLS and maze[nr][nc] == 0:
                    nr, nc = nr + dx, nc + dy
                    curr_distance += 1

                new_distance = distances[row][col] + curr_distance
                if distances[nr - dx][nc - dy] > new_distance:
                    distances[nr - dx][nc - dy] = new_distance
                    heapq.heappush(priority_queue, [nr - dx, nc - dy, new_distance])

        res = distances[destination[0]][destination[1]]
        return res if res != float('inf') else -1