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

Array
BFS
DFS
Matrix
Union Find

TIME

O(m * n)

SPACE

O(m * n)

Intuition

BFS/DFS with connection validation. When moving between cells, both cells must have compatible street types that connect to each other.

Solution

Street Connections

Define which directions each street type connects:

Street 1: left, right      (←→)
Street 2: up, down         (↑↓)
Street 3: left, down       (←↓)
Street 4: right, down      (→↓)
Street 5: left, up         (←↑)
Street 6: right, up        (→↑)

Movement Validation

When moving from cell A to cell B in direction D:

A must have exit in direction D
B must have entrance from opposite direction

# directions: 0=up, 1=right, 2=down, 3=left
connections = {
    1: {1, 3},      # left, right
    2: {0, 2},      # up, down
    3: {2, 3},      # down, left
    4: {1, 2},      # right, down
    5: {0, 3},      # up, left
    6: {0, 1},      # up, right
}
opposite = {0: 2, 1: 3, 2: 0, 3: 1}

# Can move from (i,j) in direction d?
if d in connections[grid[i][j]]:
    ni, nj = i + di[d], j + dj[d]
    if opposite[d] in connections[grid[ni][nj]]:
        # Valid move!

Complexity

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

Edge Cases

Single cell grid → always true
Start cell doesn't connect anywhere
Dead ends before reaching destination

Code

from typing import List
from collections import deque


class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        """
        1391. Check if There is a Valid Path in a Grid
        Time: O(m * n)
        Space: O(m * n)
        """
        m, n = len(grid), len(grid[0])

        if m == 1 and n == 1:
            return True

        # Directions: 0=up, 1=right, 2=down, 3=left
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        opposite = {0: 2, 1: 3, 2: 0, 3: 1}

        # Which directions each street connects
        connections = {
            1: {1, 3},  # left, right
            2: {0, 2},  # up, down
            3: {2, 3},  # down, left
            4: {1, 2},  # right, down
            5: {0, 3},  # up, left
            6: {0, 1},  # up, right
        }

        visited = [[False] * n for _ in range(m)]
        queue = deque([(0, 0)])
        visited[0][0] = True

        while queue:
            i, j = queue.popleft()

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

            for d, (di, dj) in enumerate(directions):
                # Check if current cell connects in this direction
                if d not in connections[grid[i][j]]:
                    continue

                ni, nj = i + di, j + dj

                if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj]:
                    # Check if neighbor connects back
                    if opposite[d] in connections[grid[ni][nj]]:
                        visited[ni][nj] = True
                        queue.append((ni, nj))

        return False

import java.util.*;

/**
 * 1391. Check if There is a Valid Path in a Grid
 * Time: O(m * n)
 * Space: O(m * n)
 */
class Solution {
    public boolean hasValidPath(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        if (m == 1 && n == 1) {
            return true;
        }

        // Directions: 0=up, 1=right, 2=down, 3=left
        int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        int[] opposite = {2, 3, 0, 1};

        // Which directions each street connects (as bitmask)
        // bit 0=up, bit 1=right, bit 2=down, bit 3=left
        int[] connections = {
            0,          // placeholder for index 0
            0b1010,     // 1: right(1), left(3)
            0b0101,     // 2: up(0), down(2)
            0b1100,     // 3: down(2), left(3)
            0b0110,     // 4: right(1), down(2)
            0b1001,     // 5: up(0), left(3)
            0b0011      // 6: up(0), right(1)
        };

        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int i = cell[0], j = cell[1];

            if (i == m - 1 && j == n - 1) {
                return true;
            }

            for (int d = 0; d < 4; d++) {
                // Check if current cell connects in this direction
                if ((connections[grid[i][j]] & (1 << d)) == 0) {
                    continue;
                }

                int ni = i + dirs[d][0], nj = j + dirs[d][1];

                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
                    // Check if neighbor connects back
                    if ((connections[grid[ni][nj]] & (1 << opposite[d])) != 0) {
                        visited[ni][nj] = true;
                        queue.offer(new int[]{ni, nj});
                    }
                }
            }
        }

        return false;
    }
}