Check If There Is A Valid Path In A Grid - Leetcode Solution

Problem Statement:

Given a m x n grid. Each cell of the grid represents a street. The street of Grid[i][j] can be:

1 which means a street connecting the left cell;  
2 which means a street connecting the right cell;  
3 which means a street connecting the top cell;  
4 which means a street connecting the bottom cell;  
5 which means a street connecting the left cell and the top cell;  
6 which means a street connecting the right cell and the top cell;  
7 which means a street connecting the left cell and the bottom cell;  
8 which means a street connecting the right cell and the bottom cell;  

You will initially start at the street of grid[0][0]. A valid path in the grid is a path which starts from the top-left corner (0,0) and ends at the bottom-right corner (m-1, n-1). The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

Solution:

To determine if there is a valid path in a grid, we need to traverse the grid from the starting point to the ending point. However, there are some restrictions on the path that we can take. We can only move in the direction that is allowed by the cell that we are currently in. For example, if we are in a cell where the street is connected to the left cell and the bottom cell, we can only move to the left or to the bottom.

To solve this problem, we can use a depth-first search algorithm to explore all possible paths from the starting point to the ending point. However, we need to make sure that we are not exploring paths that are not valid. If we encounter a cell where we are not able to move in any direction that is allowed, we need to backtrack and explore other paths.

We can use a recursive function to implement the depth-first search algorithm. The function should take in the current position, the direction that we are coming from, and the grid as inputs. The function should return true if there is a valid path from the current position to the ending point, and false otherwise.

Here is the code implementation:

def hasValidPath(grid):
    m = len(grid)
    n = len(grid[0])
    
    def isValid(i, j, direction):
        street = grid[i][j]
        if street == 1:
            return direction in {'left', 'right'}
        elif street == 2:
            return direction in {'left', 'right'}
        elif street == 3:
            return direction in {'up', 'down'}
        elif street == 4:
            return direction in {'up', 'down'}
        elif street == 5:
            return direction in {'right', 'up'} if direction == 'right' else direction in {'left', 'down'}
        elif street == 6:
            return direction in {'left', 'up'} if direction == 'left' else direction in {'right', 'down'}
        elif street == 7:
            return direction in {'left', 'down'} if direction == 'down' else direction in {'right', 'up'}
        elif street == 8:
            return direction in {'right', 'down'} if direction == 'down' else direction in {'left', 'up'}

    def dfs(i, j, direction, visited):
        if (i, j) == (m-1, n-1):
            return True
        
        if (i, j) in visited:
            return False
        
        visited.add((i, j))
        
        if direction is None:
            if isValid(i, j, 'left'):
                if dfs(i, j-1, 'right', visited):
                    return True
            if isValid(i, j, 'right'):
                if dfs(i, j+1, 'left', visited):
                    return True
            if isValid(i, j, 'up'):
                if dfs(i-1, j, 'down', visited):
                    return True
            if isValid(i, j, 'down'):
                if dfs(i+1, j, 'up', visited):
                    return True
        else:
            if direction == 'left':
                if isValid(i, j, 'left'):
                    if dfs(i, j-1, 'right', visited):
                        return True
            elif direction == 'right':
                if isValid(i, j, 'right'):
                    if dfs(i, j+1, 'left', visited):
                        return True
            elif direction == 'up':
                if isValid(i, j, 'up'):
                    if dfs(i-1, j, 'down', visited):
                        return True
            elif direction == 'down':
                if isValid(i, j, 'down'):
                    if dfs(i+1, j, 'up', visited):
                        return True
        
        visited.remove((i, j))
        return False
    
    return dfs(0, 0, None, set())

Time Complexity Analysis:

The time complexity of the depth-first search algorithm is O(mn) since we are only exploring each cell once. The time complexity of the isValid function is O(1) since we are only performing constant operations. Therefore, the overall time complexity of the solution is O(mn).

Space Complexity Analysis:

The space complexity of the depth-first search algorithm is O(mn) since we are using a set to keep track of the visited cells. The space complexity of the isValid function is O(1) since we are only storing a few variables. Therefore, the overall space complexity of the solution is O(mn).

Conclusion:

In this problem, we needed to check if there is a valid path in a grid that connects the starting point to the ending point. We used a depth-first search algorithm to explore all possible paths, and we made sure that we are only exploring paths that are valid. The time complexity of the solution is O(mn), and the space complexity of the solution is also O(mn).

1