346. Check if There is a Valid Path in a Grid

Each cell type connects exactly two of the four neighbours. From (0, 0), do a DFS that walks onto a neighbouring cell only when both sides agree their streets connect.

Approach

1. For each street type, list its two outgoing directions (e.g. type 1 connects left + right).
2. Run DFS from (0, 0): for each direction allowed by the current cell, step to the neighbour and check that the neighbour's street also points back; if yes and not visited, recurse.
3. Return True if (m - 1, n - 1) is ever reached.

Complexity

• Time: O(m · n) — each cell visited at most once.
• Space: O(m · n) — visited matrix and recursion stack.

class Solution {
    private static final int[][][] streets = {
        {},
        {{0, -1}, {0, 1}},
        {{-1, 0}, {1, 0}},
        {{0, -1}, {1, 0}},
        {{0, 1}, {1, 0}},
        {{0, -1}, {-1, 0}},
        {{0, 1}, {-1, 0}}
    };

    public boolean hasValidPath(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        return dfs(grid, visited, 0, 0, m, n);
    }

    private boolean dfs(int[][] grid, boolean[][] visited, int r, int c, int m, int n) {
        if (r == m - 1 && c == n - 1) return true;
        visited[r][c] = true;
        for (int[] dir : streets[grid[r][c]]) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) continue;
            boolean connects = false;
            for (int[] ndir : streets[grid[nr][nc]]) {
                if (ndir[0] == -dir[0] && ndir[1] == -dir[1]) {
                    connects = true;
                    break;
                }
            }
            if (connects && dfs(grid, visited, nr, nc, m, n)) return true;
        }
        return false;
    }
}

Each cell type lists exactly two neighbour directions it connects to. So the streets form an undirected graph: there's an edge between cells A and B if and only if A's street points to B and B's street points back to A. The question becomes a standard reachability check from the top-left to the bottom-right — easy with BFS.

Encoding the streets

Each street type connects exactly two of the four neighbours. Pre-compute a small lookup table:

A traversal A → B is legal iff:

• (dr, dc) is in streets[A], and
• (-dr, -dc) is in streets[B] (B's street points back to A).

The second check is what makes streets form an undirected graph: both endpoints must agree.

Steps

1. Build the lookup table above.
2. Initialise visited (an m × n boolean grid), mark (0, 0) visited, and a queue containing (0, 0).
3. While the queue is non-empty:
   • Pop (r, c). If it's (m - 1, n - 1), return True.
   • For each direction (dr, dc) in streets[grid[r][c]]:
     • Compute neighbour (nr, nc).
     • Skip if out of bounds or already visited.
     • If (-dr, -dc) is in streets[grid[nr][nc]], mark visited and enqueue (nr, nc).
4. If the queue empties without reaching the goal, return False.

Walk-through

Grid:

[[2, 4, 3],
 [6, 5, 2]]

Cells:

• (0,0) type 2 (up ↔ down).
• (0,1) type 4 (right + down).
• (0,2) type 3 (left + down).
• (1,0) type 6 (right + up).
• (1,1) type 5 (left + up).
• (1,2) type 2 (up ↔ down).

BFS from (0,0):

• (0,0) type 2 — exits up and down. Up out of bounds. Down → (1,0) type 6 — does it have (-1, 0) (up)? Type 6 = right + up = (0,1), (-1,0). Yes. Visit (1,0).
• (1,0) type 6 — exits right and up. Right → (1,1) type 5 — does it have (0,-1) (left)? Type 5 = left + up = (0,-1), (-1,0). Yes. Visit (1,1). Up → (0,0) already visited.
• (1,1) type 5 — exits left and up. Left → (1,0) visited. Up → (0,1) type 4 — does it have (1,0) (down)? Type 4 = right + down. Yes. Visit (0,1).
• (0,1) type 4 — exits right and down. Right → (0,2) type 3 — does it have (0,-1) (left)? Type 3 = left + down. Yes. Visit (0,2). Down → (1,1) visited.
• (0,2) type 3 — exits left and down. Left → (0,1) visited. Down → (1,2) type 2 — does it have (-1, 0) (up)? Type 2 has (-1, 0). Yes. Visit (1,2) — that's (m-1, n-1). Return True. ✓

Why DFS-vs-BFS doesn't matter for correctness

We're only asking reachability, not shortest path or counts. Both DFS and BFS visit every reachable cell and only those — they reach the goal iff the goal is reachable. We pick BFS here because Python's default recursion limit is 1000 and a 300 × 300 grid can have a path longer than that, leading to a RecursionError for DFS.

Edge cases

• m == 1 and n == 1: the start is the goal. BFS pops (0,0) and returns True immediately.
• A street that points off the grid: the bounds check filters it out.
• A street pointing into a non-matching neighbour: the back-check filters it out (the neighbour's street doesn't reciprocate).

Complexity

• Time: O(m · n) — every cell visited at most once.
• Space: O(m · n) — visited grid and the BFS queue.