Check if There is a Valid Path in a Grid

medium graph dfs bfs matrix

Problem

You are given an m×n grid where each cell holds a street number from 1 to 6. Each street type fixes exactly two openings on its sides: 1 connects left↔right, 2 connects up↔down, 3 connects left↔down, 4 connects right↔down, 5 connects left↔up, and 6 connects right↔up. You may walk from a cell to a neighbor only when both tiles have an opening facing each other. Starting at the upper-left cell (0, 0), decide whether a valid path of connected streets reaches the lower-right cell (m−1, n−1).

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

Outputtrue

The streets connect (0,0)→(1,0)→(1,1)→(0,1)→(0,2)→(1,2), so the target is reachable.

grid rows ';' separated, streets 1-6 csv

def has_valid_path(grid):
    m, n = len(grid), len(grid[0])
    # opening directions per street: L,R,U,D as (dr,dc)
    ports = {1: [(0,-1),(0,1)], 2: [(-1,0),(1,0)], 3: [(0,-1),(1,0)],
             4: [(0,1),(1,0)], 5: [(0,-1),(-1,0)], 6: [(0,1),(-1,0)]}
    seen = [[False]*n for _ in range(m)]
    stack = [(0, 0)]
    seen[0][0] = True
    while stack:
        r, c = stack.pop()
        if r == m - 1 and c == n - 1:
            return True
        for dr, dc in ports[grid[r][c]]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc] \
               and (-dr, -dc) in ports[grid[nr][nc]]:
                seen[nr][nc] = True
                stack.append((nr, nc))
    return False

function hasValidPath(grid) {
  const m = grid.length, n = grid[0].length;
  const ports = {1:[[0,-1],[0,1]], 2:[[-1,0],[1,0]], 3:[[0,-1],[1,0]],
                 4:[[0,1],[1,0]], 5:[[0,-1],[-1,0]], 6:[[0,1],[-1,0]]};
  const seen = Array.from({length: m}, () => Array(n).fill(false));
  const stack = [[0, 0]];
  seen[0][0] = true;
  while (stack.length) {
    const [r, c] = stack.pop();
    if (r === m - 1 && c === n - 1) return true;
    for (const [dr, dc] of ports[grid[r][c]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr][nc]
          && ports[grid[nr][nc]].some(p => p[0] === -dr && p[1] === -dc)) {
        seen[nr][nc] = true;
        stack.push([nr, nc]);
      }
    }
  }
  return false;
}

class Solution {
    public boolean hasValidPath(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][][] ports = {{}, {{0,-1},{0,1}}, {{-1,0},{1,0}}, {{0,-1},{1,0}},
                           {{0,1},{1,0}}, {{0,-1},{-1,0}}, {{0,1},{-1,0}}};
        boolean[][] seen = new boolean[m][n];
        Deque<int[]> stack = new ArrayDeque<>();
        stack.push(new int[]{0, 0});
        seen[0][0] = true;
        while (!stack.isEmpty()) {
            int[] cur = stack.pop();
            int r = cur[0], c = cur[1];
            if (r == m - 1 && c == n - 1) return true;
            for (int[] d : ports[grid[r][c]]) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr][nc]
                    && connects(ports[grid[nr][nc]], -d[0], -d[1])) {
                    seen[nr][nc] = true;
                    stack.push(new int[]{nr, nc});
                }
            }
        }
        return false;
    }
    private boolean connects(int[][] p, int dr, int dc) {
        for (int[] d : p) if (d[0] == dr && d[1] == dc) return true;
        return false;
    }
}

bool hasValidPath(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<pair<int,int>>> ports = {{}, {{0,-1},{0,1}}, {{-1,0},{1,0}},
        {{0,-1},{1,0}}, {{0,1},{1,0}}, {{0,-1},{-1,0}}, {{0,1},{-1,0}}};
    vector<vector<bool>> seen(m, vector<bool>(n, false));
    vector<pair<int,int>> stack = {{0, 0}};
    seen[0][0] = true;
    while (!stack.empty()) {
        auto [r, c] = stack.back(); stack.pop_back();
        if (r == m - 1 && c == n - 1) return true;
        for (auto [dr, dc] : ports[grid[r][c]]) {
            int nr = r + dr, nc = c + dc;
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) continue;
            for (auto [pr, pc] : ports[grid[nr][nc]])
                if (pr == -dr && pc == -dc) {
                    seen[nr][nc] = true;
                    stack.push_back({nr, nc});
                }
        }
    }
    return false;
}

Explanation

Every cell is a fixed piece of street with exactly two openings. The number just tells you which two sides are open. The whole problem is really a plain graph reachability question once we figure out the edges: from any cell, which neighbors can you actually walk to?

The key rule is that an edge between two adjacent cells exists only when both halves agree. It is not enough that my tile opens toward you; your tile must also open back toward me. If I have an opening pointing right but the cell to my right has no opening on its left, the streets do not meet and there is no connection.

So we store, for each street type, its two opening directions as (dr, dc) offsets. To test a move from the current cell in direction (dr, dc), we check two things: the current tile lists (dr, dc) as an opening (it does, since we only loop over its own openings), and the neighbor lists the opposite direction (-dr, -dc) as one of its openings. When both hold, the pieces interlock and we can cross.

With the edge test in hand, we run an ordinary DFS (a stack works just as well as recursion, and BFS would be equally fine) from (0, 0), marking cells as seen so we never revisit. If we ever pop the bottom-right cell (m−1, n−1), a valid path exists and we return true. If the stack empties without reaching it, no connected route exists and we return false.

Trace the example grid = [[2,4,3],[6,5,2]]. Start at street 2 (up/down) at (0,0); its down opening meets street 6 below, whose up opening faces back, so we step to (1,0). Street 6 (right/up) connects right to street 5 at (1,1); street 5 (left/up) connects up to street 4 at (0,1); street 4 (right/down) connects right to street 3 at (0,2); and street 3 (left/down) connects down to street 2 at (1,2) — the target. The answer is true.

Time: O(m·n) Space: O(m·n)