Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: The Maze II
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

There is a ball in a maze with empty spaces (0) and walls (1). The ball can move up, down, left, or right through empty spaces but won't stop until it hits a wall. When the ball stops, it can change direction.

Given an m x n maze, the ball's start position, and the destination, where start = [start<sub>row</sub>, start<sub>col</sub>] and destination = [destination<sub>row</sub>, destination<sub>col</sub>], find the shortest distance for the ball to reach the destination. If the ball can't reach the destination, return -1.

The distance is the number of empty spaces traveled by the ball from the start (excluded) to the destination (included).

Examples

Example 1

  • Input: start = [0, 1], destination = [4, 4], 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]]
  • Expected Output: 7
Image
  • Justification: The ball travels from the start (0,1) down to (2,1), right to (2, 2), down to (4, 2), and right to (4, 4) in 7 moves.

Example 2

  • Input: start = [0, 0], destination = [4, 4], maze = 
    [[0, 0, 0, 0, 0],
 [1, 1, 1, 1, 0],
 [0, 0, 0, 0, 0],
 [0, 1, 1, 1, 0],
 [0, 0, 0, 0, 0]]
  • Expected Output: 8
Image
  • Justification: The ball travels from (0,0) right to (0,4), down to (4,4) in 8 moves.

Example 3:

  • Input: start = [0, 1], destination = [3, 1], maze = 
    [[0, 0, 1, 0, 0],
 [0, 1, 1, 0, 0],
 [0, 1, 0, 0, 1],
 [1, 0, 0, 1, 0],
 [0, 0, 0, 0, 0]]
  • Expected Output: -1
  • Justification: The ball cannot reach the destination (3,1) due to walls blocking the path.

Constraints:

  • m == maze.length
  • n == maze[i].length
  • 1 <= m, n <= 100
  • maze[i][j] is 0 or 1.
  • start.length == 2
  • destination.length == 2
  • 0 <= start<sub>row</sub>, destination<sub>row</sub> < m
  • 0 <= start<sub>col</sub>, destination<sub>col</sub> < n
  • Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
  • The maze contains at least 2 empty spaces.

Solution

To solve this problem, we can use Dijkstra's algorithm. This algorithm is suitable for finding the shortest path in a graph with non-negative edge weights. The maze can be thought of as a graph where each cell is a node, and the ball's movement through empty spaces can be considered as edges with weights equal to the distance traveled. Dijkstra's algorithm ensures that we find the shortest distance from the start position to the destination by exploring the least costly paths first.

The approach involves using a priority queue to keep track of the positions in the maze and their respective distances from the start. Each time we explore a new position, we roll the ball in all possible directions until it hits a wall, then add the new stopping positions to the priority queue with the updated distances. This process continues until we either find the shortest path to the destination or exhaust all possible paths.

Step-by-step Algorithm

  1. Initialize Distances:

    • Create a distances array with dimensions matching the maze, initializing all values to infinity.
    • Set the distance to the start position as 0.

  2. Priority Queue:

    • Create a priority queue to store positions along with their current distances from the start.
    • Add the start position to the queue with distance 0.

  3. Direction Vectors:

    • Define possible movement directions: right, down, left, and up.

  4. Process the Queue:

    • While the queue is not empty, repeat the following steps:
      • Extract the position with the smallest distance from the queue.
      • If the current position is the destination, return the current distance as the result.

  5. Explore Directions:

    • For each of the four possible directions:
      • Roll the ball in the current direction until it hits a wall.
      • Calculate the distance traveled in the current direction.
      • Check if the new position (after hitting the wall) has a shorter distance compared to previously known distances:
        • If so, update the distance for the new position.
        • Add the new position along with the updated distance to the priority queue.

  6. Terminate:

    • If the queue is empty and the destination has not been reached, return -1 indicating the destination is unreachable.

Algorithm Walkthrough

Using the input:

  • start = [0, 1]
  • destination = [4, 4]
  • 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]]

  1. Initialization:

    • distances = 
      [[inf, 0, inf, inf, inf],
 [inf, inf, inf, inf, inf],
 [inf, inf, inf, inf, inf],
 [inf, inf, inf, inf, inf],
 [inf, inf, inf, inf, inf]]
    • Priority Queue: [(0, 1, 0)] (initial position with distance 0)

  2. Process the Queue:

    • Extract (0, 1, 0) from the queue.
    • Current position: (0, 1), distance: 0

  3. Explore Directions:

    Right:

    • Roll right from (0, 1) to (0, 2), but it's a wall, so stop at (0, 1).
    • Distance remains 0 (no change, already processed).

    Down:

    • Roll down from (0, 1) to (1, 1), then to (2, 1), stop at (2, 1).
    • Distance traveled = 2.
    • Update distance for (2, 1): 
      [[inf, 0, inf, inf, inf],
 [inf, inf, inf, inf, inf],
 [inf, 2, inf, inf, inf],
 [inf, inf, inf, inf, inf],
 [inf, inf, inf, inf, inf]]
    • Add to queue: [(2, 1, 2)]

    Left:

    • Roll left from (0, 1) to (0, 0), stop at (0, 0).
    • Distance traveled = 1.
    • Update distance for (0, 0): 
      [[1, 0, inf, inf, inf],
 [inf, inf, inf, inf, inf],
 [inf, 2, inf, inf, inf],
 [inf, inf, inf, inf, inf],
 [inf, inf, inf, inf, inf]]
    • Add to queue: [(0, 0, 1)]

    Up:

    • Roll up from (0, 1), but it's a boundary, so stop at (0, 1).
    • Distance remains 0 (no change, already processed).

  4. Process the Queue:

    • Extract (0, 0, 1) from the queue.
    • Current position: (0, 0), distance: 1

  5. Explore Directions:

    Right:

    • Roll right from (0, 0) to (0, 1), stop at (0, 1).
    • Distance remains 1 (no change, already processed).

    Down:

    • Roll down from (0, 0) to (1, 0), then to (2, 0), stop at (2, 0).
    • Distance traveled = 3.
    • Update distance for (2, 0): 
      [[1, 0, inf, inf, inf],
 [inf, inf, inf, inf, inf],
 [3, 2, inf, inf, inf],
 [inf, inf, inf, inf, inf],
 [inf, inf, inf, inf, inf]]
    • Add to queue: [(2, 0, 3)]

    Left:

    • Roll left from (0, 0), but it's a boundary, so stop at (0, 0).
    • Distance remains 1 (no change, already processed).

    Up:

    • Roll up from (0, 0), but it's a boundary, so stop at (0, 0).
    • Distance remains 1 (no change, already processed).

  6. Process the Queue:

    • Extract (2, 1, 2) from the queue.
    • Current position: (2, 1), distance: 2

  7. Explore Directions:

    Right:

    • Roll right from (2, 1) to (2, 2), stop at (2, 2).
    • Distance traveled = 3.
    • Update distance for (2, 2): 
      [[1, 0, inf, inf, inf],
 [inf, inf, inf, inf, inf],
 [3, 2, 3, inf, inf],
 [inf, inf, inf, inf, inf],
 [inf, inf, inf, inf, inf]]
    • Add to queue: [(2, 2, 3)]

    Down:

    • Roll down from (2, 1) to (3, 1), but it's a wall, so stop at (2, 1).
    • Distance remains 2 (no change, already processed).

    Left:

    • Roll left from (2, 1) to (2, 0), stop at (2, 0).
    • Distance remains 3 (no change, already processed).

    Up:

    • Roll up from (2, 1) to (1, 1), then to (0, 1), stop at (0, 1).
    • Distance remains 2 (no change, already processed).

  8. Process the Queue:

    • Extract (2, 0, 3) from the queue.
    • Current position: (2, 0), distance: 3

  9. Explore Directions:

    Right:

    • Roll right from (2, 0) to (2, 1), stop at (2, 1).
    • Distance remains 3 (no change, already processed).

    Down:

    • Roll down from (2, 0) to (3, 0). Here, we have wall at (3, 0). So, stop.

    Left:

    • Roll left from (2, 0), but it's a boundary, so stop at (2, 0).
    • Distance remains 3 (no change, already processed).

    Up:

    • Roll up from (2, 0) to (1, 0), then to (0, 0), stop at (0, 0).
    • Distance remains 3 (no change, already processed).

  10. Process the Queue:

    • Extract (2, 2, 3) from the queue.
    • Current position: (2, 2), distance: 3

  11. Explore Directions:

    Right:

    • Roll right from (2, 2) to (2, 3), but it's a wall, so stop at (2, 2).
    • Distance remains 3 (no change, already processed).

    Down:

    • Roll down from (2, 2) to (3, 2), then to (4, 2), stop at (4, 2).
    • Distance traveled = 5.
    • Update distance for (4, 2): 
      [[1, 0, inf, inf, inf],
 [inf, inf, inf, inf, inf],
 [3, 2, 3, inf, inf],
 [inf, inf, inf, inf, inf],
 [6, inf, 5, inf, inf]]
    • Add to queue: [(4, 2, 5)]

    Left:

    • Roll left from (2, 2) to (2, 1), stop at (2, 1).
    • Distance remains 3 (no change, already processed).

    Up:

    • Roll up from (2, 2) to (1, 2), then to (0, 2), stop at (0, 2).
    • Distance remains 3 (no change, already processed).

  12. Process the Queue:

    • Extract (4, 2, 5) from the queue.
    • Current position: (4, 2), distance: 5

  13. Explore Directions:

    Right:

    • Roll right from (4, 2) to (4, 3), then to (4, 4), stop at (4, 4).
    • Distance traveled = 7.
    • Update distance for (4, 4): 
      [[1, 0, inf, inf, inf],
 [inf, inf, inf, inf, inf],
 [3, 2, 3, inf, inf],
 [inf, inf, inf, inf, inf],
 [inf, inf, 5, 6, 7]]
    • Add to queue: [(4, 4, 7)]

    Down:

    • Roll down from (4, 2), but it's a boundary, so stop at (4, 2).
    • Distance remains 5 (no change, already processed).

    Left:

    • Roll left from (4, 2) to (4, 1), then to (4, 0), stop at (4, 0).
    • Add (4, 0, 7) into the queue.

    Up:

    • Roll up from (4, 2) to (3, 2), then to (2, 2), stop at (2, 2).
    • Distance remains 5 (no change, already processed).

  14. Process the Queue:

    • Extract (4, 4, 7) from the queue.
    • Current position: (4, 4), distance: 7
    • Destination reached with distance 7. Return the result.

Result

The shortest distance for the ball to stop at the destination [4, 4] starting from [0, 1] is 7.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • The primary operations involve exploring each cell in the maze, which are m * n cells where m is the number of rows and n is the number of columns.
  • For each cell, we explore up to 4 possible directions (up, down, left, right) until hitting a wall.
  • Each cell is added to the priority queue and can be processed once, leading to O(m * n log(m * n)) time for the priority queue operations.

Therefore, the time complexity is O(m * n log(m * n)).

Space Complexity

  • We use a distance matrix to keep track of the shortest distance to each cell, which takes O(m * n) space.
  • The priority queue also holds at most m * n elements, which also requires #O(m * n)$ space.

Therefore, the space complexity is O(m * n).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible