Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Neighboring street cells connect only when both tiles have openings toward each other. Treating valid connections as graph edges reduces the task to reachability, but checking only the current tile's exit would incorrectly allow one-sided connections.

Approach

Map each street type to its two exit directions and define each direction's opposite. Traverse from the top-left cell, considering only in-bounds, unvisited neighbors reached through an exit. Enter a neighbor only if its tile also contains the opposite exit, marking it before further exploration. Return true upon reaching the bottom-right cell and false if traversal exhausts the reachable component. Python uses recursive DFS while JavaScript uses an explicit stack; a one-cell grid succeeds immediately.

class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        dirs = {
            1: [(0, 1), (0, -1)],
            2: [(-1, 0), (1, 0)],
            3: [(0, -1), (1, 0)],
            4: [(0, 1), (1, 0)],
            5: [(-1, 0), (0, -1)],
            6: [(-1, 0), (0, 1)]
        }

        opposite = {
            (1, 0): (-1, 0),
            (-1, 0): (1, 0),
            (0, 1): (0, -1),
            (0, -1): (0, 1)
        }

        def dfs(i, j):
            if i == n - 1 and j == m - 1: return True

            for di, dj in dirs[grid[i][j]]:
                ni, nj = i + di, j + dj
                if ni < 0 or ni == n or nj < 0 or nj == m or (ni, nj) in seen: continue
                if opposite[(di, dj)] in dirs[grid[ni][nj]]:
                    seen.add((ni, nj))
                    if dfs(ni, nj): return True
            
            return False
        
        n = len(grid)
        m = len(grid[0])
        seen = {(0, 0)}
        return dfs(0, 0)

Complexity analysis

For an R × C grid, traversal visits each reachable cell at most once and checks two exits per cell. Time is O(RC) and auxiliary space is O(RC) for the visited set and explicit JavaScript stack. The unchanged Python implementation uses recursive DFS, so an allowed serpentine path through nearly 90000 cells can exceed its runtime stack.