Check if There is a Valid Path in a Grid

What the problem is really asking

Each grid cell is a small street tile. A path is valid only when the current tile opens toward the next cell and the next tile opens back toward the current cell.

So the grid is really an undirected graph:

• every cell is a node
• an edge exists between two adjacent cells only when both street pieces connect to each other
• the answer is whether (0, 0) and (m - 1, n - 1) are in the same connected component

This is a static connectivity problem because the grid never changes after it is given.

Street directions as bits

Label the four directions like this:

     0
     ^
     |
3 <--+--> 1
     |
     v
     2

Now represent each street type as a 4-bit mask:

1: left + right = 1010
2: up + down    = 0101
3: left + down  = 1100
4: right + down = 0110
5: left + up    = 1001
6: right + up   = 0011

If a cell connects in direction d, then the neighbor in that direction must connect back in direction (d + 2) % 4.

That one rule replaces all the hard-coded "if this is type 1 and neighbor is type 3 or 5..." logic.

Approach

1. Create a Union Find structure with m * n nodes.
2. Convert every cell (row, col) to a one-dimensional id: row * n + col.
3. For every cell, inspect the four possible directions.
4. If the current cell has an opening in direction d, check the adjacent cell.
5. If the adjacent cell exists and has the opposite opening, union both cell ids.
6. At the end, return whether the ids for (0, 0) and (m - 1, n - 1) have the same root.

class Solution {
    private int[] parent;
    private int[] size;
    private final int[] patterns = {0, 0b1010, 0b0101, 0b1100, 0b0110, 0b1001, 0b0011};
    private final int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public boolean hasValidPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        parent = new int[m * n];
        size = new int[m * n];

        for (int i = 0; i < m * n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                int pattern = patterns[grid[row][col]];

                for (int dir = 0; dir < 4; dir++) {
                    if ((pattern & (1 << dir)) == 0) {
                        continue;
                    }

                    int nextRow = row + dirs[dir][0];
                    int nextCol = col + dirs[dir][1];

                    if (
                        nextRow >= 0 && nextRow < m &&
                        nextCol >= 0 && nextCol < n &&
                        (patterns[grid[nextRow][nextCol]] & (1 << ((dir + 2) % 4))) != 0
                    ) {
                        union(row * n + col, nextRow * n + nextCol);
                    }
                }
            }
        }

        return find(0) == find(m * n - 1);
    }

    private int find(int node) {
        if (parent[node] != node) {
            parent[node] = find(parent[node]);
        }
        return parent[node];
    }

    private void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA == rootB) {
            return;
        }

        if (size[rootA] < size[rootB]) {
            int temp = rootA;
            rootA = rootB;
            rootB = temp;
        }

        parent[rootB] = rootA;
        size[rootA] += size[rootB];
    }
}

Dry run

Take the first example:

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

Cell (0, 0) has street type 2, so it opens up and down. The upward neighbor is outside the grid, but the downward neighbor (1, 0) is type 6, which opens back upward. We union those two cells.

From (1, 0), type 6 opens right and up. The right neighbor (1, 1) is type 5, which opens back left, so they are unioned too.

The same connection rule continues through (1, 1) -> (0, 1) -> (0, 2) -> (1, 2). By the end, the first and last cells share one component, so the answer is true.

For the second example:

grid = [
  [1, 2, 1],
  [1, 2, 1]
]

The start cell (0, 0) is type 1, which only opens left and right. Its right neighbor is type 2, which only opens up and down, so it does not open back left. No edge is created from the start cell, and the answer is false.

Why Union Find works here

Union Find answers exactly the question this problem becomes after graph construction:

Are two nodes in the same connected component?

We do not need the actual path. We only need to know whether some sequence of valid street-to-street connections can link the start to the finish.

Common mistakes

1. Checking only the current cell's street

If a street opens right, that is not enough. The right neighbor must also open left. A move is valid only when both tiles agree.

2. Mixing up opposite directions

With the direction order up, right, down, left, the opposite of d is (d + 2) % 4.

3. Treating the street number as a direction

Street values 1 through 6 are tile types, not directions. Use a mapping from tile type to its two open directions.

Complexity

Let m be the number of rows and n be the number of columns.

Time Complexity: O(m * n * alpha(m * n))

Each cell checks four directions, and every valid connection performs a Union Find operation. With path compression and union by size, each operation is effectively constant.

Space Complexity: O(m * n)

Union Find stores parent and size arrays for all cells.