{x}
blog image

Check if There is a Valid Path in a Grid

You are given an m x n grid. Each cell of grid represents a street. The street of grid[i][j] can be:

  • 1 which means a street connecting the left cell and the right cell.
  • 2 which means a street connecting the upper cell and the lower cell.
  • 3 which means a street connecting the left cell and the lower cell.
  • 4 which means a street connecting the right cell and the lower cell.
  • 5 which means a street connecting the left cell and the upper cell.
  • 6 which means a street connecting the right cell and the upper cell.

You will initially start at the street of the upper-left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (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.

 

Example 1:

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).

Example 2:

Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)

Example 3:

Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • 1 <= grid[i][j] <= 6

Solution Explanation:

This problem asks whether a valid path exists in a grid, starting from the top-left corner and ending at the bottom-right corner, following the directions indicated by the numbers in each cell. The solution uses a Union-Find algorithm for efficiency.

Approach:

  1. Union-Find Data Structure: A Union-Find data structure is used to efficiently track connected components in the grid. Each cell is initially considered a separate component. The find function determines the root of a component (which represents the component itself).

  2. Connecting Components: The algorithm iterates through each cell in the grid. Based on the number in the cell (representing the street direction), it connects the cell to its adjacent cells if a valid path exists between them. The left, right, up, and down functions handle this connection by using the find function to identify the component roots and then setting the root of one component to be the root of the other (union).

  3. Check for Connectivity: After processing all cells, the algorithm checks if the top-left cell (0, 0) and the bottom-right cell (m-1, n-1) belong to the same component using find. If they do, it means there is a valid path, and the function returns true; otherwise, it returns false.

Time Complexity:

The time complexity is dominated by the nested loops iterating through the grid, which takes O(mn) time, where 'm' and 'n' are the dimensions of the grid. The find operation in a Union-Find data structure with path compression has an amortized time complexity of almost O(1), so the union operations also take O(mn) time in total. Therefore, the overall time complexity is O(m*n).

Space Complexity:

The space complexity is dominated by the p array used in the Union-Find data structure, which has a size of mn. Therefore, the space complexity is **O(mn)**.

Code Explanation (Python):

class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        p = list(range(m * n))  # Initialize parent array for Union-Find
 
        def find(x):  # Find the root of a component
            if p[x] != x:
                p[x] = find(p[x])  # Path compression for efficiency
            return p[x]
 
        # Functions to connect adjacent cells based on street directions
        def left(i, j):
            if j > 0 and grid[i][j - 1] in (1, 4, 6):
                p[find(i * n + j)] = find(i * n + j - 1)
 
        def right(i, j):
            if j < n - 1 and grid[i][j + 1] in (1, 3, 5):
                p[find(i * n + j)] = find(i * n + j + 1)
 
        def up(i, j):
            if i > 0 and grid[i - 1][j] in (2, 3, 4):
                p[find(i * n + j)] = find((i - 1) * n + j)
 
        def down(i, j):
            if i < m - 1 and grid[i + 1][j] in (2, 5, 6):
                p[find(i * n + j)] = find((i + 1) * n + j)
 
        # Iterate through the grid and connect components
        for i in range(m):
            for j in range(n):
                e = grid[i][j]
                if e == 1:
                    left(i, j)
                    right(i, j)
                elif e == 2:
                    up(i, j)
                    down(i, j)
                # ... (rest of the cases for e = 3, 4, 5, 6)
 
        # Check if start and end cells are in the same component
        return find(0) == find(m * n - 1)

The Java, C++, and Go code implementations follow a very similar structure and logic to the Python code, employing the same Union-Find algorithm with path compression for optimal performance. The only differences are in syntax and data structure representations specific to each language.