The Maze - Leetcode Solution

Problem Description:

You are given a map of a maze, represented as a binary 2D array. 1 represents a wall and 0 represents a path. You start at the top-left corner and the exit is at the bottom-right corner. You can move towards the right, left, up, or down. You cannot move through walls. Determine the shortest path to the exit, if one exists. If there are multiple shortest paths, return any one of them.

Example: Input: map = [[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]]

Output: [(0,0), (0,1), (0,2), (1,2), (2,2), (3,2), (4,2), (4,3), (4,4)]

Approach:

This problem can be approached using BFS (Breadth First Search) Algorithm. We can start from the top-left corner as the starting point. We can keep track of visited points to avoid revisiting them. When we reach the bottom-right corner, we can exit the algorithm and return the path that we took. We can take any path that we want, as we are asked to provide any shortest path, based on the given constraints.

Steps:

1. Check if the starting point (0,0) is a wall or not. If it is a wall, return an empty path as there is no way out.
2. Create a queue and add the starting point to it.
3. Create a visited set and add the starting point to it.
4. While the queue is not empty: a. Dequeue the front element from the queue and store its coordinates. b. If the current point is the exit point, return the path that we took to reach it. c. Check if there are any valid adjacent points that we can travel to (not a wall and not visited). If there are, enqueue them into the queue and store the path we took to reach that point. d. Mark the current point as visited.
5. If we reach here, then there is no path from the starting point to the exit point. Return an empty path.

Code:

Here is the implementation of the code mentioned above:

def maze(map):
    #dimensions of the input map
    n, m = len(map), len(map[0])
    
    #check if starting point is a wall or not
    if map[0][0] == 1:
        return []
    
    #create a queue and add start to it
    q = [(0,0)]
    #set to keep track of visited points
    visited = set(q)
      
    #while queue is not empty
    while q:
        #dequeue from queue and store its coordinates
        x, y = q.pop(0)
        
        #return the path when exit is reached
        if (x,y) == (n-1,m-1):
            res = []
            #backtrack the path from exit while adding to res array
            while (x,y) != (0,0):
                res.append((x,y))
                x, y = parent[x][y]
            res.append((0,0))
            res.reverse()
            return res
        
        #check for adjacent points that we can move to
        for i, j in [(1,0),(-1,0),(0,1),(0,-1)]:
            new_x, new_y = x+i, y+j
            if 0 <= new_x < n and 0 <= new_y < m and (new_x,new_y) not in visited and not map[new_x][new_y]:
                #add adjacent to queue and mark it as visited
                q.append((new_x,new_y))
                visited.add((new_x,new_y))
                #store the path we took to reach this point
                parent[new_x][new_y] = (x,y)
                
    #when queue is empty, there is no way to exit. Return an empty path
    return []

Time Complexity: O(N*M) where N is the number of rows and M is the number of columns of the input map.

Space Complexity: O(N*M) where N is the number of rows and M is the number of columns of the input map. This is because, in the worst-case scenario, we might have to store all the points in the visited set and the queue.

1