505. The Maze II


Problem Description

In the given LeetCode problem, we are presented with a maze that is a grid of cells, where each cell can either be an empty space represented by a 0 or a wall represented by a 1. A ball is placed in this maze and can roll in one of four directions: up, down, left, or right. The ball will continue rolling in its chosen direction until it encounters a wall, at which point it comes to a stop and can be redirected in a new direction.

Our task is to find the shortest distance for the ball to travel from a starting cell (start) to a destination cell (destination). The start and destination are given as coordinate pairs indicating the row and column of the cell in the grid. The distance is measured as the number of empty cells the ball passes through along its way, not including the starting cell but including the destination cell.

We must consider that the ball cannot stop or change direction until it hits a wall, and the maze's borders are also considered to be walls. If it's not possible for the ball to reach the destination, we should return -1. Otherwise, we should return the minimum number of steps required for the ball to reach the destination.

Intuition

The intuition behind the solution is to use Breadth-First Search (BFS) to explore the maze. BFS is an ideal choice here because it ensures that we visit cells in increasing order of their distance from the start. We aim to find the shortest path, and BFS helps explore all paths in a systematic way, level by level, until we reach the destination.

We start by initializing a queue and a distance matrix. The distance matrix stores the shortest distance from the start to every cell in the maze. Each cell starts with a distance value of infinity, except for the starting cell, which has a distance of zero.

The key part of the search involves rolling the ball in each possible direction until it hits a wall. For each direction, we keep track of the rolling distance, and if we can reach a cell with a shorter distance than previously recorded, we update the distance matrix and enqueue that cell for further exploration. We continue this process until there are no more cells left to explore.

By the end of the BFS, the distance matrix will contain the minimum distances to each cell from the starting position, if they are reachable. We then inspect the distance value at the destination cell. If it is still infinity, this means the destination is not reachable, and we return -1. Otherwise, we return the distance value at the destination cell as the shortest path length.

Learn more about Depth-First Search, Breadth-First Search, Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The solution to the problem uses the Breadth-First Search (BFS) algorithm, which works particularly well for finding the shortest path in un-weighted graphs or grids, like our maze. The essential components of BFS include a queue to keep track of cells to visit next and a matrix to keep track of distances to each cell.

Here's a step-by-step breakdown of the solution:

  1. Initialize Data Structures:

    • We start by initializing the queue q and distance matrix dist. The queue will store cells that we need to visit, formatted as (row, column) tuples. The distance matrix is the same size as the maze and is initialized with inf (infinity), other than the starting cell, which is set to 0.
  2. Define Directions:

    • The dirs tuple contains the changes in row and column coordinates corresponding to the four possible movement directions (up, right, down, and left).
  3. Begin BFS:

    • The BFS loop starts by repeatedly dequeuing a cell (i, j) from q. For each dequeued cell:
      • We loop over the possible directions the ball could roll using the coordinates from the dirs tuple.
  4. Roll the Ball:

    • For each direction, simulate the ball's roll until it hits a wall by updating its current position (x, y) as long as the next cell in the maze is a 0 (an empty space) and is within the bounds of the maze. The counter k is used to count the number of steps the ball takes.
  5. Update Distances:

    • When the ball stops, we check if the distance to the current stopping cell (x, y) is greater than the distance k. If it is, we found a shorter path to this cell. We update dist[x][y] with the new shorter distance and enqueue the stopping cell to explore subsequent paths from this new position.
  6. Check for Destination:

    • Finally, if the destination's distance is no longer infinity, we've found at least one way to reach it, and dist[di][dj] contains the length of the shortest path. If it's still infinity, then there is no way to reach the destination, and we return -1.

The use of the pairwise function from itertools is assumed in the given code, but it might need to be translated to a loop or another form of iteration if it's unavailable.

This BFS solution ensures that we only update distances for cells that can be reached with a shorter path than previously recorded. Hence, we accomplish finding the shortest path by exploring cells in layers, always ensuring the shortest paths have been considered first.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Consider the following maze:

1Maze:
2[0, 0, 1, 0, 0]
3[0, 0, 0, 0, 0]
4[0, 1, 0, 1, 0]
5[1, 1, 0, 1, 1]
6[0, 0, 0, 0, 0]

And let's say the start is at the top left corner (0,0) and the destination is at the bottom right corner (4,4).

  1. Initialize Data Structures:
    • Queue q: [(0,0)]
    • Distance matrix dist: Initialized with infinity, but dist[0][0] will be 0 since it's our start.
1dist:
2[0, ∞, ∞, ∞, ∞]
3[∞, ∞, ∞, ∞, ∞]
4[∞, ∞, ∞, ∞, ∞]
5[∞, ∞, ∞, ∞, ∞]
6[∞, ∞, ∞, ∞, ∞]
  1. Define Directions:

    • dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
  2. Begin BFS:

    • Dequeue (0, 0) from q and check all four directions.
  3. Roll the Ball:

    • Roll right: stops at (0, 2) because of a wall. Distance traveled: 2.
      • Update dist[0][2] = 2 and enqueue (0, 2).
    • Roll down: stops at (2,0) because of a wall. Distance traveled: 2.
      • Update dist[2][0] = 2 and enqueue (2, 0).
1After first dequeue, dist:
2[0, ∞,  2, ∞, ∞]
3[∞, ∞, ∞, ∞, ∞]
4[2, ∞, ∞, ∞, ∞]
5[∞, ∞, ∞, ∞, ∞]
6[∞, ∞, ∞, ∞, ∞]
  1. Update Distances:

    • Roll from (0, 2) and (2, 0) and update distances as you find shorter paths. The ball cannot move left or up from either of these positions because they’re not deeper in the maze, which avoids backtracking.
  2. Check for Destination:

    • Continue BFS until you reach (4, 4) or determine the destination is unreachable.

Continuing this process, we explore all possible paths in the maze. Depending on the further rolls and distance updates, we might end up with something like this:

1Final dist:
2[0, 1,  2, 5, 6]
3[1, 2, 3, 4, 5]
4[2, ∞, 4, ∞, 6]
5[∞, ∞, 5, ∞, ∞]
6[∞, ∞, 6, 7, 8]

In the end, we see dist[4][4] is 8, so the shortest path from (0,0) to (4,4) is 8 steps. If dist[4][4] remained infinity, we would conclude the destination is unreachable and return -1.

Solution Implementation

1from collections import deque
2from itertools import pairwise
3from math import inf
4
5class Solution:
6    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
7        # Get the dimensions of the maze
8        rows, cols = len(maze), len(maze[0])
9
10        # Directions for moving up, right, down, and left
11        directions = (-1, 0, 1, 0, -1)
12
13        # Starting point
14        start_i, start_j = start
15
16        # Destination point
17        dest_i, dest_j = destination
18
19        # Queue for BFS
20        queue = deque([(start_i, start_j)])
21
22        # Initialize a distance matrix with infinity values
23        distance = [[inf] * cols for _ in range(rows)]
24        distance[start_i][start_j] = 0  # Starting point distance is 0
25
26        # Perform BFS
27        while queue:
28            i, j = queue.popleft()
29          
30            # Using pairwise to iterate through the directions
31            for a, b in pairwise(directions):
32                x, y, current_dist = i, j, distance[i][j]
33
34                # Move in the current direction until hitting a wall
35                while 0 <= x + a < rows and 0 <= y + b < cols and maze[x + a][y + b] == 0:
36                    x += a
37                    y += b
38                    current_dist += 1
39
40                # If minimum distance can be updated
41                if current_dist < distance[x][y]:
42                    distance[x][y] = current_dist
43                    # Add new position to the queue for further exploration
44                    queue.append((x, y))
45
46        # If the destination is unreachable, return -1; otherwise, return the distance
47        return -1 if distance[dest_i][dest_j] == inf else distance[dest_i][dest_j]
48
1import java.util.Arrays;
2import java.util.ArrayDeque;
3import java.util.Deque;
4
5class Solution {
6
7    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
8        // Dimensions of the maze
9        int rows = maze.length, columns = maze[0].length;
10
11        // Representation of the infinity for unreachable cells
12        final int INFINITY = Integer.MAX_VALUE;
13
14        // Array storing the shortest distance to each cell from the start
15        int[][] distance = new int[rows][columns];
16        for (int[] row : distance) {
17            Arrays.fill(row, INFINITY);
18        }
19
20        // Coordinates of the start position
21        int startX = start[0], startY = start[1];
22        // Coordinates of the destination
23        int destX = destination[0], destY = destination[1];
24
25        // Start cell has a distance of 0 from itself
26        distance[startX][startY] = 0;
27
28        // Queue for Breadth-First Search (BFS)
29        Deque<int[]> queue = new ArrayDeque<>();
30        queue.offer(new int[] {startX, startY});
31
32        // Direction vectors representing up, right, down, left movements
33        int[] directions = {-1, 0, 1, 0, -1};
34
35        // BFS loop running until the queue is empty
36        while (!queue.isEmpty()) {
37            int[] point = queue.poll();
38            int currentX = point[0], currentY = point[1];
39          
40            // Try each direction from current cell
41            for (int d = 0; d < 4; ++d) {
42                int nextX = currentX, nextY = currentY;
43                int count = distance[currentX][currentY]; // Distance if we move this way
44                int deltaX = directions[d], deltaY = directions[d + 1];
45
46                // Move in the current direction as long as it's a valid and empty space
47                while (nextX + deltaX >= 0 && nextX + deltaX < rows
48                        && nextY + deltaY >= 0 && nextY + deltaY < columns
49                        && maze[nextX + deltaX][nextY + deltaY] == 0) {
50                    nextX += deltaX;
51                    nextY += deltaY;
52                    ++count;
53                }
54
55                // If this path offers a shorter distance, update the distance array and queue the next cell
56                if (count < distance[nextX][nextY]) {
57                    distance[nextX][nextY] = count;
58                    queue.offer(new int[] {nextX, nextY});
59                }
60            }
61        }
62
63        // If the destination's distance is still INFINITY, it's unreachable; otherwise, return the distance
64        return distance[destX][destY] == INFINITY ? -1 : distance[destX][destY];
65    }
66}
67
1#include <vector>
2#include <queue>
3#include <cstring>
4using namespace std;
5
6class Solution {
7public:
8    // Function to find the shortest distance in a maze from a start point to a destination.
9    int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
10        int rows = maze.size(), cols = maze[0].size(); // Number of rows and columns in the maze.
11        int distances[rows][cols];
12        memset(distances, 0x3f, sizeof(distances)); // Initialize all distances to a high value.
13      
14        // Starting position.
15        int startRow = start[0], startCol = start[1];
16        // Destination position.
17        int destRow = destination[0], destCol = destination[1];
18      
19        distances[startRow][startCol] = 0; // Distance to the start point is 0.
20        queue<pair<int, int>> queue;
21        queue.emplace(startRow, startCol); // Put the start position in the queue.
22
23        // Directions for moving up, right, down, left.
24        int dirs[5] = {-1, 0, 1, 0, -1};
25      
26        while (!queue.empty()) {
27            // Get the current position from the queue.
28            auto [currentRow, currentCol] = queue.front();
29            queue.pop();
30
31            // Explore all possible directions.
32            for (int d = 0; d < 4; ++d) {
33                int x = currentRow, y = currentCol;
34                int dist = distances[currentRow][currentCol];
35                int rowDir = dirs[d], colDir = dirs[d + 1];
36                // Move in the current direction until we hit a wall or the edge of the maze.
37                while (x + rowDir >= 0 && x + rowDir < rows &&
38                       y + colDir >= 0 && y + colDir < cols &&
39                       maze[x + rowDir][y + colDir] == 0) {
40                    x += rowDir;
41                    y += colDir;
42                    ++dist;
43                }
44                // Update the distance if a shorter path is found.
45                if (dist < distances[x][y]) {
46                    distances[x][y] = dist;
47                    // Put the new position into the queue.
48                    queue.emplace(x, y);
49                }
50            }
51        }
52        // Return the shortest distance to the destination or -1 if not reachable.
53        return distances[destRow][destCol] == 0x3f3f3f3f ? -1 : distances[destRow][destCol];
54    }
55};
56
1function shortestDistance(maze: number[][], start: number[], destination: number[]): number {
2    // Maze dimensions
3    const rows = maze.length;
4    const cols = maze[0].length;
5  
6    // Initialize distance array with Infinity, signifying unvisited cells
7    const distances: number[][] = Array.from({ length: rows }, () =>
8        Array.from({ length: cols }, () => Infinity),
9    );
10
11    // Deconstruct start coordinates for readability
12    const [startRow, startCol] = start;
13
14    // Deconstruct destination coordinates for readability
15    const [destRow, destCol] = destination;
16
17    // Starting cell has a distance of 0 as it's our starting point
18    distances[startRow][startCol] = 0;
19
20    // Queue for breadth-first search, starting with the start cell
21    const queue: number[][] = [[startRow, startCol]];
22
23    // Directions for up, right, down, and left
24    const directions = [-1, 0, 1, 0, -1];
25
26    // Process each cell in the queue
27    while (queue.length > 0) {
28        // Current cell
29        const [currentRow, currentCol] = queue.shift()!;
30
31        // Explore all possible directions
32        for (let d = 0; d < 4; d++) {
33            // Initialize new positions to the current cell's coordinates
34            let [row, col, count] = [currentRow, currentCol, distances[currentRow][currentCol]];
35            const [deltaRow, deltaCol] = [directions[d], directions[d + 1]];
36
37            // Keep rolling the ball until we hit a wall
38            while (
39                row + deltaRow >= 0 && row + deltaRow < rows &&
40                col + deltaCol >= 0 && col + deltaCol < cols &&
41                maze[row + deltaRow][col + deltaCol] === 0
42            ) {
43                row += deltaRow;
44                col += deltaCol;
45                count++;
46            }
47
48            // If the new cell's distance is less than previously recorded, update it
49            if (count < distances[row][col]) {
50                distances[row][col] = count;
51                queue.push([row, col]); // Add new position to queue for further exploration
52            }
53        }
54    }
55
56    // Return the shortest distance to the destination. If Infinity, the destination is unreachable, hence return -1.
57    return distances[destRow][destCol] === Infinity ? -1 : distances[destRow][destCol];
58}
59

Time and Space Complexity

Time Complexity

The time complexity of the code primarily depends on two factors:

  1. How often each cell is visited.
  2. The number of possible directions to explore from each cell.

The algorithm uses Breadth-First Search (BFS) to explore the cells, starting from the start cell. BFS usually has a time complexity of O(V + E), with V being the number of vertices (cells in this case) and E being the number of edges (possible moves from one cell to another).

However, in this problem, thanks to the while loop inside the BFS that keeps rolling the ball until it hits a wall, the actual number of edges E can be less than 4V (since from any cell the ball can potentially only move in 4 directions initially). Furthermore, the algorithm also tracks the distance to each cell in an attempt to only queue cells that lead to a shorter path, making the potential number of cells to be revisited smaller. Despite this, the worst case can still potentially visit each cell multiple times due to multiple paths leading to the same cell.

Therefore, the time complexity is O(V * W), where V is the number of cells (m * n), and W is the maximum number of times a cell may be visited, which is bounded by the number of cells that can be reached from any given cell (i.e., in the worst case, each cell is visited from each of its four directions).

Hence, the overall time complexity is O(m * n * W).

Space Complexity

The space complexity of the algorithm is influenced by:

  1. The distance matrix dist which stores the distance to each cell, having a size of m * n.
  2. The queue q used for BFS which in the worst case can store all the vertices.

As a result, the space complexity of the code is O(m * n) due to the dist matrix, as this is likely to outweigh the space used by the queue in most instances.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Recommended Readings


Got a question?Β Ask the Monster AssistantΒ anything you don't understand.

Still not clear? Ask in the Forum, Β DiscordΒ orΒ SubmitΒ the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns
←
↑πŸͺ„