Problem Statement in English

You’re given a m x n grid. The grid is represented by a 2D array of integers where each integer represents a type of street. The streets are connected in the following way:

  • Street type 1: connects left and right.
  • Street type 2: connects up and down.
  • Street type 3: connects left and down.
  • Street type 4: connects right and down.
  • Street type 5: connects left and up.
  • Street type 6: connects right and up.

You start at the top-left corner of the grid (0, 0) and you want to reach the bottom-right corner of the grid (m - 1, n - 1). You can only move in the direction of the streets. For example, if you’re on a street type 1, you can only move left or right.

Return true if there is a valid path from the top-left corner to the bottom-right corner, or false otherwise.

Approach

We need to map the directions for each street type and then perform a depth-first search (DFS) or breadth-first search (BFS) to find if there is a valid path from the top-left corner to the bottom-right corner.

We will also maintain a set of seen nodes to avoid cycles.

For each cell, we will check the possible directions based on the street type and then check if we can move to the next cell in that direction. If we can, we will also check if the next cell has a street that connects back to the current cell. If yes, then we can navigate there!

And we’re done!

Solution in Python


class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        m = len(grid)
        n = len(grid[0])

        directions = {
            1: [(0, -1), (0, 1)],
            2: [(1, 0), (-1, 0)],
            3: [(1, 0), (0, -1)],
            4: [(0, 1), (1, 0)],
            5: [(0, -1), (-1, 0)],
            6: [(0, 1), (-1, 0)],
        }

        seen = set()
        stack = [(0, 0)]

        while stack:
            i, j = stack.pop()

            if i == m - 1 and j == n - 1:
                return True

            if (i, j) not in seen:
                seen.add((i, j))

            for dx, dy in directions[grid[i][j]]:
                nx, ny = i + dx, j + dy

                if (nx, ny) not in seen and 0 <= nx < m and 0 <= ny < n:
                    for dx, dy in directions[grid[nx][ny]]:
                        if nx + dx == i and ny + dy == j:
                            stack.append((nx, ny))

        return False

Complexity

  • Time: $O(m \times n)$
    Since we may need to visit each cell at most once.

  • Space: $O(m \times n)$
    Since we may need to store all cells in the seen set and the stack.

And we are done.