We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check if There is a Valid Path in a Grid

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each cell has specific street connections that dictate valid movements.
  • The problem can be viewed as a graph traversal where each cell is a node.
  • Valid movements depend on the current cell's street type and the neighboring cells' street types.
  • Both Depth-First Search (DFS) and Breadth-First Search (BFS) can be applied to explore possible paths.

Space and Time Complexity

Time Complexity: O(m * n) - Each cell is visited once. Space Complexity: O(m * n) - For the visited cells tracking.

Solution

The solution leverages Depth-First Search (DFS) to explore the grid starting from the upper-left corner. A stack or recursion is used to traverse the cells. During traversal, we check the current cell's street type to determine valid movements to neighboring cells. We keep track of visited cells to avoid cycles and ensure that we do not revisit cells. If we reach the bottom-right cell, we return true; if all possible paths are exhausted, we return false.

Code Solutions

def hasValidPath(grid):
    m, n = len(grid), len(grid[0])
    directions = {
        1: [(0, 1), (0, -1)],  # left-right
        2: [(1, 0), (-1, 0)],  # up-down
        3: [(0, -1), (1, 0)],  # left-down
        4: [(0, 1), (1, 0)],   # right-down
        5: [(0, -1), (-1, 0)], # left-up
        6: [(0, 1), (-1, 0)]   # right-up
    }
    
    visited = set()

    def canReach(x, y):
        if (x, y) in visited:
            return False
        if x < 0 or x >= m or y < 0 or y >= n:
            return False
        if (x, y) == (m - 1, n - 1):
            return True
        
        visited.add((x, y))
        for dx, dy in directions[grid[x][y]]:
            nx, ny = x + dx, y + dy
            if (0 <= nx < m and 0 <= ny < n and
                (dx, dy) in directions[grid[nx][ny]]):
                if canReach(nx, ny):
                    return True
        return False

    return canReach(0, 0)
← Back to All Questions