490. The Maze


Problem Description

In this problem, we're given a 2D array that represents a maze, where 0s represent empty spaces and 1s represent walls. The maze is surrounded by walls on all borders. A ball can roll through the maze, but it only stops moving when it hits a wall. Once it's stopped, it can then be rolled again in any of the four cardinal directions (up, down, left, right). The goal is to determine if there is a way to move the ball from its start position to a specified destination by only rolling it in such a way that it stops at the destination. The start position and destination are given as [row, column] coordinates. The problem asks us to return true if the ball can reach the destination and stop there, and false otherwise.

Intuition

The solution to this problem involves exploring the maze to find if there is a path to the destination. Exploring a maze is a classic problem that is usually solved using graph traversal algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS). The intuition behind using BFS in this particular problem is that we want to explore all possible paths where the ball can roll until it hits a wall.

The main idea is to simulate the rolling of the ball. We start at the initial position and roll the ball in all possible directions until it hits a wall. Once it comes to a stop, we check if the current stopping point is the destination. If it's not, we treat this stopping point as a new start point and continue to roll the ball in all four directions. We repeat this process until we either reach the destination or all possible paths have been explored without reaching it.

We need to keep track of the positions we have already visited to prevent infinite loops. This is because without tracking, we might keep revisiting the same positions over and over again. For this purpose, we use a set to store visited positions.

By using BFS with a queue and a visited set, we can systematically explore the maze and check if a path to the destination exists.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The implementation of the aforementioned BFS approach is straightforward. To explain how the solution works, let's break it down step by step:

  1. Queue Initialization: We initialize a queue q for the BFS with the starting position of the ball. This queue will be used to store the positions from where we need to continue exploring further.

  2. Visited Set: To keep track of the positions we have visited so far to avoid re-processing, we initialize a set vis.

  3. BFS Loop: We enter a loop to process each element in the queue until it's empty, which means we've exhausted all possible movements. For each position taken from the queue: a. We calculate potential new positions by moving the ball in all four possible directions until it hits a wall. b. For each of the four directions, we ensure that the movement is within the bounds of the maze and we are moving into empty space (0). c. As soon as the ball stops due to hitting a wall, we check if the stopped position is the destination. If it is, we've found a path, and we return true. d. If the new stopped position is not the destination and hasn't been visited yet, we add it to the visited set and the queue for further exploration.

  4. Directions Representation: The directions in which the ball can move are represented by the vectors [[0, -1], [0, 1], [-1, 0], [1, 0]], which correspond to left, right, up, and down movements, respectively.

  5. Exploring Paths: For each position discovered, the loop continues exploring further by seeing where the ball can go next from these new positions, until it either reaches the destination or there are no more positions to explore (the queue becomes empty).

  6. Return False: If the queue is exhausted without finding the destination, the function returns false, signifying that there is no path that leads to the destination.

The choice of BFS in this case is strategic, as it allows us to explore the maze level by level, considering the shortest paths first and ensuring that once we reach the destination, we've found the optimal solution (should one exist).

Here's the implementation as provided in the reference document:

1class Solution:
2    def hasPath(
3        self, maze: List[List[int]], start: List[int], destination: List[int]
4    ) -> bool:
5        m, n = len(maze), len(maze[0])
6        q = deque([start])
7        rs, cs = start
8        vis = {(rs, cs)}
9        while q:
10            i, j = q.popleft()
11            for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
12                x, y = i, j
13                while 0 <= x + a < m and 0 <= y + b < n and maze[x + a][y + b] == 0:
14                    x, y = x + a, y + b
15                if [x, y] == destination:
16                    return True
17                if (x, y) not in vis:
18                    vis.add((x, y))
19                    q.append((x, y))
20        return False

This code clearly follows the BFS paradigm, and it allows us to see a practical implementation of the intuition discussed earlier.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take an example maze and walk through the solution using the BFS approach detailed in the content above.

Suppose we have the following 2D maze where S is the start position, D is the destination, 0 represents open space, and 1 represents a wall:

11 1 1 1 1
21 0 0 0 1
31 0 1 0 1
41 S 1 D 1
51 1 1 1 1

The start position is marked as [3, 1] and the destination is [3, 3]. We want to find if there's a path for the ball to roll from S to D.

  1. Queue Initialization: Initialize the queue with the start position (3, 1).

  2. Visited Set: Initialize the visited set and add the start position to it.

  3. BFS Loop: Now, we start processing the position (3, 1) and we need to explore all four directions. We'll simulate the rolling of the ball until it hits a wall:

    • Rolling left is not an option since (3, 0) is a wall.
    • Rolling right ends up at (3, 2), just before the wall.
    • Rolling up isn't possible due to hitting a wall immediately.
    • Rolling down hits a wall immediately.
  4. We then mark (3, 2) as visited and add it to the queue if it's not already visited. In this case, it's a new position so we add it.

  5. The queue now has (3, 2), and we pick this and repeat the process. Rolling right from (3, 2) makes the ball stop at (3, 3), which is our destination D.

  6. Once we hit the destination, we return True, indicating that there is indeed a path from S to D.

If we continue the loop without finding the destination, we will eventually run out of positions to check, which would compel us to return False, indicating there's no such path. However, in this example, since we did reach the destination, we successfully exit the loop with the correct outcome.

Solution Implementation

1from collections import deque
2from typing import List
3
4class Solution:
5    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
6        # Get the dimensions of the maze.
7        rows, cols = len(maze), len(maze[0])
8      
9        # Initialize a queue to perform BFS and add the starting point.
10        queue = deque([start])
11      
12        # Set to keep track of visited positions to avoid loops.
13        visited = set()
14        visited.add(tuple(start))
15      
16        # Perform BFS from the start position.
17        while queue:
18            current_position = queue.popleft()
19            row, col = current_position
20          
21            # Explore all possible directions: left, right, up, down.
22            for direction_row, direction_col in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
23                new_row, new_col = row, col
24              
25                # Move in the current direction as far as possible until hitting a wall.
26                while 0 <= new_row + direction_row < rows and 0 <= new_col + direction_col < cols \
27                        and maze[new_row + direction_row][new_col + direction_col] == 0:
28                    new_row += direction_row
29                    new_col += direction_col
30              
31                # If the destination is reached, return True.
32                if [new_row, new_col] == destination:
33                    return True
34              
35                # If the new position has not been visited, mark as visited and add to queue.
36                if (new_row, new_col) not in visited:
37                    visited.add((new_row, new_col))
38                    queue.append((new_row, new_col))
39      
40        # If no path is found after exploring all possibilities, return False.
41        return False
42
1class Solution {
2    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
3        // Dimensions of the maze
4        int numRows = maze.length;
5        int numCols = maze[0].length;
6
7        // Visited positions marker
8        boolean[][] visited = new boolean[numRows][numCols];
9
10        // Mark the start position as visited
11        visited[start[0]][start[1]] = true;
12
13        // Initialize a queue for BFS
14        Deque<int[]> queue = new LinkedList<>();
15        queue.offer(start);
16
17        // Direction vectors: up, right, down, left
18        int[] directions = {-1, 0, 1, 0, -1};
19
20        // Perform BFS to find the path
21        while (!queue.isEmpty()) {
22            int[] position = queue.poll();
23            int currentRow = position[0], currentCol = position[1];
24
25            // Traverse in all four directions
26            for (int k = 0; k < 4; ++k) {
27                int nextRow = currentRow, nextCol = currentCol;
28                // Direction modifiers for both row and column
29                int rowInc = directions[k], colInc = directions[k + 1];
30              
31                // Roll the ball until a wall is hit
32                while (
33                    nextRow + rowInc >= 0 && nextRow + rowInc < numRows &&
34                    nextCol + colInc >= 0 && nextCol + colInc < numCols && 
35                    maze[nextRow + rowInc][nextCol + colInc] == 0
36                ) {
37                    nextRow += rowInc;
38                    nextCol += colInc;
39                }
40              
41                // If the destination is found, return true
42                if (nextRow == destination[0] && nextCol == destination[1]) {
43                    return true;
44                }
45              
46                // If the new position is not visited, mark it visited and add to queue
47                if (!visited[nextRow][nextCol]) {
48                    visited[nextRow][nextCol] = true;
49                    queue.offer(new int[] {nextRow, nextCol});
50                }
51            }
52        }
53      
54        // Return false if the destination is not reachable
55        return false;
56    }
57}
58
1class Solution {
2public:
3    // Function to check if there is a path in the maze from start to destination.
4    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
5        int rows = maze.size();    // Number of rows in the maze.
6        int cols = maze[0].size(); // Number of columns in the maze.
7      
8        // Queue to perform BFS with the initial position being the start.
9        queue<vector<int>> queue;
10        queue.push(start);
11      
12        // Visited array to keep track of visited nodes.
13        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
14        visited[start[0]][start[1]] = true;
15      
16        // 4 possible directions to move: up, right, down, left.
17        vector<int> directions = {-1, 0, 1, 0, -1};
18      
19        // Start BFS.
20        while (!queue.empty()) {
21            vector<int> position = queue.front();
22            queue.pop();
23            int currentRow = position[0], currentCol = position[1];
24          
25            // Explore all possible 4 directions.
26            for (int k = 0; k < 4; ++k) {
27                int newRow = currentRow, newCol = currentCol;
28                int rowDir = directions[k], colDir = directions[k + 1];
29              
30                // Roll the ball until it hits a wall.
31                while (newRow + rowDir >= 0 && newRow + rowDir < rows &&
32                       newCol + colDir >= 0 && newCol + colDir < cols &&
33                       maze[newRow + rowDir][newCol + colDir] == 0) {
34                    newRow += rowDir;
35                    newCol += colDir;
36                }
37              
38                // Check if the new position is the destination.
39                if (newRow == destination[0] && newCol == destination[1]) return true;
40              
41                // If the new position has not been visited, mark as visited and enqueue it.
42                if (!visited[newRow][newCol]) {
43                    visited[newRow][newCol] = true;
44                    queue.push({newRow, newCol});
45                }
46            }
47        }
48      
49        // Return false if destination is not reachable.
50        return false;
51    }
52};
53
1// Represents the maze as a 2D array of numbers, 1 for walls and 0 for paths.
2type Maze = number[][];
3
4// Represents a position in the maze with format [row, column].
5type Position = [number, number];
6
7// Function signature to check if there is a path in the maze from start to destination.
8function hasPath(maze: Maze, start: Position, destination: Position): boolean {
9    const rows = maze.length; // Number of rows in the maze.
10    const cols = maze[0].length; // Number of columns in the maze.
11
12    // Queue to perform BFS, initialized with the starting position.
13    const queue: Position[] = [start];
14
15    // Visited matrix to keep track of visited positions.
16    const visited: boolean[][] = Array.from({ length: rows }, () => Array(cols).fill(false));
17    visited[start[0]][start[1]] = true;
18
19    // Possible directions to move: left, down, right, and up.
20    const directions: number[] = [-1, 0, 1, 0, -1];
21
22    // Start BFS exploration.
23    while (queue.length > 0) {
24        const [currentRow, currentCol] = queue.shift()!; // Assume queue is not empty and position is defined.
25
26        // Explore in all four directions.
27        for (let k = 0; k < 4; ++k) {
28            let newRow = currentRow, newCol = currentCol;
29            const rowDir = directions[k], colDir = directions[k + 1];
30
31            // Roll the ball until it hits a wall or the edge of the maze.
32            while (
33                newRow + rowDir >= 0 && newRow + rowDir < rows &&
34                newCol + colDir >= 0 && newCol + colDir < cols &&
35                maze[newRow + rowDir][newCol + colDir] === 0
36            ) {
37                newRow += rowDir;
38                newCol += colDir;
39            }
40
41            // If the new position is the destination, return true.
42            if (newRow === destination[0] && newCol === destination[1]) {
43                return true;
44            }
45
46            // If the new position has not been visited, mark as visited and enqueue it.
47            if (!visited[newRow][newCol]) {
48                visited[newRow][newCol] = true;
49                queue.push([newRow, newCol]);
50            }
51        }
52    }
53
54    // If the destination was not reached, return false.
55    return false;
56}
57

Time and Space Complexity

The given code is an implementation of the Breadth-First Search (BFS) algorithm, which is used to determine whether there is a path from the start to the destination in a given maze using possible movements up, down, left, or right. It stops movement in one direction when it hits a wall or the edge of the maze.

Time Complexity

The time complexity of this function is O(m * n), where m is the number of rows, and n is the number of columns in the maze. This is because, in the worst case, the algorithm may explore each cell in the maze once. Each cell is added to the queue only once, and each roll in one of four directions continues until it hits a wall, but the rolling action does not increase the total number of cells visited. Each possible space is processed once, so at most, the algorithm will perform m * n operations.

Space Complexity

The space complexity of the function is also O(m * n). This is due to the storage required for the visited set vis, which in the worst case may contain every cell in the maze. Moreover, the queue q may also store a significant number of positions although not more than m * n. However since we only store each cell at most once, the space complexity remains O(m * n) overall.

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


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following is a good use case for backtracking?


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

🪄