# Check if There is a Valid Path in a Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-if-there-is-a-valid-path-in-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/check-if-there-is-a-valid-path-in-a-grid
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Matrix
**Companies:** [Robinhood](https://scaleengineer.com/companies/robinhood)
---
## Problem
You are given an `m x n` `grid`. Each cell of `grid` represents a street. The street of `grid[i][j]` can be:

* `1` which means a street connecting the left cell and the right cell.
* `2` which means a street connecting the upper cell and the lower cell.
* `3` which means a street connecting the left cell and the lower cell.
* `4` which means a street connecting the right cell and the lower cell.
* `5` which means a street connecting the left cell and the upper cell.
* `6` which means a street connecting the right cell and the upper cell.
![](https://assets.glich.co/dsa/check-if-there-is-a-valid-path-in-a-grid/image0.png) 

You will initially start at the street of the upper-left cell `(0, 0)`. A valid path in the grid is a path that starts from the upper left cell `(0, 0)` and ends at the bottom-right cell `(m - 1, n - 1)`. **The path should only follow the streets**.

**Notice** that you are **not allowed** to change any street.

Return `true` _if there is a valid path in the grid or_ `false` _otherwise_.

**Example 1:**

![](https://assets.glich.co/dsa/check-if-there-is-a-valid-path-in-a-grid/image1.png) 

**Input:** grid = [[2,4,3],[6,5,2]]
**Output:** true
**Explanation:** As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).

**Example 2:**

![](https://assets.glich.co/dsa/check-if-there-is-a-valid-path-in-a-grid/image2.png) 

**Input:** grid = [[1,2,1],[1,2,1]]
**Output:** false
**Explanation:** As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)

**Example 3:**

**Input:** grid = [[1,1,2]]
**Output:** false
**Explanation:** You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 300`
* `1 <= grid[i][j] <= 6`

# Approaches
## Recursive Depth-First Search (DFS)
This approach models the grid as a graph where each cell is a node. An edge exists between two adjacent cells if their respective streets connect to each other. The problem then becomes finding if a path exists from the source node (0, 0) to the destination node (m-1, n-1). DFS is a natural way to explore this path.
**Time:** O(m * n). In the worst case, we visit every cell in the grid once. · **Space:** O(m * n). This is for the `visited` array and the recursion stack. In the worst case, the recursion depth can be up to `m * n`.
**Pros:** Conceptually straightforward and easy to implement.; Follows the problem's path-finding nature directly.
**Cons:** Can lead to a `StackOverflowError` for very large grids where the path is long and winding, as the recursion depth could exceed the stack limit.
### Explanation
```java
class Solution {
    // directions[street_type - 1] = {{dr1, dc1}, {dr2, dc2}}
    private int[][][] directions = {
        {{0, -1}, {0, 1}},   // 1: left-right
        {{-1, 0}, {1, 0}},   // 2: up-down
        {{0, -1}, {1, 0}},   // 3: left-down
        {{0, 1}, {1, 0}},    // 4: right-down
        {{0, -1}, {-1, 0}},  // 5: left-up
        {{0, 1}, {-1, 0}}    // 6: right-up
    };
    private int m, n;
    private boolean[][] visited;

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

    private boolean dfs(int r, int c, int[][] grid) {
        if (r == m - 1 && c == n - 1) {
            return true;
        }
        visited[r][c] = true;

        int streetType = grid[r][c];
        for (int[] dir : directions[streetType - 1]) {
            int nr = r + dir[0];
            int nc = c + dir[1];

            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
                // Check if the next street connects back
                int nextStreetType = grid[nr][nc];
                for (int[] backDir : directions[nextStreetType - 1]) {
                    if (nr + backDir[0] == r && nc + backDir[1] == c) {
                        if (dfs(nr, nc, grid)) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- We model the grid as a graph where each cell is a node. An edge exists between two adjacent cells if their respective streets connect to each other. The problem then becomes finding if a path exists from the source node (0, 0) to the destination node (m-1, n-1).
- We start a traversal from the cell (0, 0).
- We use a `visited` boolean grid to keep track of cells that are already part of the current exploration path to avoid cycles and redundant computations.
- The core of the approach is a recursive function, say `dfs(row, col)`, which explores paths from the current cell `(row, col)`.
- **Algorithm Steps**:
  1. Define the possible moves for each street type. A street `k` allows moves in two directions. We can store this in a 3D array, e.g., `moves[k-1] = {{dr1, dc1}, {dr2, dc2}}`.
  2. Create a recursive function `dfs(r, c, grid, visited)`.
  3. **Base Case**: If `(r, c)` is the destination `(m-1, n-1)`, a path is found, return `true`.
  4. Mark the current cell `(r, c)` as visited.
  5. Get the current street type `type = grid[r][c]`.
  6. Iterate through the two possible moves `(dr, dc)` for this `type`.
  7. For each move, calculate the neighbor's coordinates `(nr, nc) = (r + dr, c + dc)`.
  8. **Validity Checks**:
     - Check if `(nr, nc)` is within the grid boundaries.
     - Check if `(nr, nc)` has been visited.
     - **Crucially, check if the street at `(nr, nc)` connects back to `(r, c)`.** This means one of the allowed moves from `(nr, nc)` must be `(-dr, -dc)`.
  9. If the move is valid, make a recursive call `dfs(nr, nc, grid, visited)`. If this call returns `true`, it means a path to the destination was found, so propagate `true` up the call stack.
  10. The initial call is `dfs(0, 0, grid, visited)`.

## Breadth-First Search (BFS)
This approach also treats the grid as a graph and uses BFS to find a path. BFS explores the graph layer by layer from the source. It's an iterative approach using a queue, which avoids the recursion depth limitations of DFS.
**Time:** O(m * n). Each cell is enqueued and dequeued at most once. · **Space:** O(m * n). For the `visited` array and the queue. The queue can hold up to O(m * n) cells in the worst case.
**Pros:** Guaranteed to find a path if one exists.; Avoids stack overflow issues since it's iterative.; Generally more robust than recursive DFS for grid traversal problems.
**Cons:** May use more memory than DFS if the graph is wide, as the queue can grow large.
### Explanation
```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public boolean hasValidPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // directions[street_type - 1] = {{dr1, dc1}, {dr2, dc2}}
        int[][][] directions = {
            {{0, -1}, {0, 1}},   // 1: left-right
            {{-1, 0}, {1, 0}},   // 2: up-down
            {{0, -1}, {1, 0}},   // 3: left-down
            {{0, 1}, {1, 0}},    // 4: right-down
            {{0, -1}, {-1, 0}},  // 5: left-up
            {{0, 1}, {-1, 0}}    // 6: right-up
        };

        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[] curr = queue.poll();
            int r = curr[0];
            int c = curr[1];

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

            int streetType = grid[r][c];
            for (int[] dir : directions[streetType - 1]) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
                    int nextStreetType = grid[nr][nc];
                    // Check if the next street connects back to the current cell
                    for (int[] backDir : directions[nextStreetType - 1]) {
                        if (nr + backDir[0] == r && nc + backDir[1] == c) {
                            visited[nr][nc] = true;
                            queue.offer(new int[]{nr, nc});
                        }
                    }
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- BFS is an excellent algorithm for finding if a path exists in an unweighted graph. It systematically explores neighbors of the starting cell, then neighbors of those neighbors, and so on.
- We use a queue to manage the cells to visit and a `visited` grid to prevent processing the same cell multiple times.
- **Algorithm Steps**:
  1. Define the possible moves for each street type, same as in the DFS approach.
  2. Initialize a queue and add the starting cell `(0, 0)`.
  3. Initialize a `visited` boolean grid of size `m x n` and mark `(0, 0)` as visited.
  4. Loop while the queue is not empty:
     a. Dequeue a cell `(r, c)`.
     b. If `(r, c)` is the destination `(m-1, n-1)`, return `true`.
     c. Get the street type `type = grid[r][c]`.
     d. For each of the two possible moves `(dr, dc)` for this `type`:
        i. Calculate the neighbor's coordinates `(nr, nc) = (r + dr, c + dc)`.
        ii. **Validity Checks**:
            - Check if `(nr, nc)` is within grid boundaries.
            - Check if `(nr, nc)` has been visited.
            - Check if the street at `(nr, nc)` connects back to `(r, c)`.
        iii. If the move is valid, enqueue `(nr, nc)` and mark it as visited.
  5. If the loop finishes, it means the destination was not reachable from the source. Return `false`.

## Union-Find (Disjoint Set Union)
This approach reframes the problem from path-finding to a connectivity problem. The Union-Find data structure is highly optimized for determining if elements belong to the same connected component. We can iterate through the grid, uniting cells that have valid street connections. Finally, we check if the start and end cells are in the same component.
**Time:** O(m * n * α(m * n)), where α is the Inverse Ackermann function. Since α grows extremely slowly, this is practically linear, i.e., O(m * n). We iterate through each cell once, and the `union` and `find` operations take nearly constant time on average. · **Space:** O(m * n) to store the `parent` array for the DSU data structure.
**Pros:** Very efficient for connectivity problems. Asymptotically, it's the fastest approach.; Elegant solution that separates the connectivity logic from the path-finding goal.
**Cons:** It always processes the entire grid, which might be slower than BFS/DFS if the connected component of the start cell is small and doesn't contain the end cell.; Slightly more complex to implement the DSU structure compared to a standard BFS/DFS.
### Explanation
```java
class Solution {
    class DSU {
        int[] parent;
        public DSU(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        public int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return parent[i] = find(parent[i]);
        }
        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
            }
        }
    }

    public boolean hasValidPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        // Ports: 0:up, 1:right, 2:down, 3:left
        int[][] ports = {
            {0, 0, 0, 0}, // dummy for 0
            {0, 1, 0, 1}, // 1: right, left
            {1, 0, 1, 0}, // 2: up, down
            {0, 0, 1, 1}, // 3: down, left
            {0, 1, 1, 0}, // 4: right, down
            {1, 0, 0, 1}, // 5: up, left
            {1, 1, 0, 0}  // 6: up, right
        };

        DSU dsu = new DSU(m * n);

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                int type = grid[r][c];
                int currentIdx = r * n + c;

                // Check connection down
                if (r + 1 < m) {
                    int downType = grid[r+1][c];
                    if (ports[type][2] == 1 && ports[downType][0] == 1) {
                        dsu.union(currentIdx, (r + 1) * n + c);
                    }
                }
                // Check connection right
                if (c + 1 < n) {
                    int rightType = grid[r][c+1];
                    if (ports[type][1] == 1 && ports[rightType][3] == 1) {
                        dsu.union(currentIdx, r * n + (c + 1));
                    }
                }
            }
        }
        
        return dsu.find(0) == dsu.find(m * n - 1);
    }
}
```
### Algorithm
- The core idea is to group all connected cells into disjoint sets. If the start cell `(0, 0)` and end cell `(m-1, n-1)` end up in the same set, a path exists between them.
- **Algorithm Steps**:
  1. Create a Union-Find (DSU) data structure for `m * n` elements. Each cell `(r, c)` is mapped to an index `r * n + c`. The DSU will need a `parent` array and optionally a `rank` or `size` array for optimization (union by rank/size).
  2. Define which street types connect to which directions. For example, a `Set` for each direction: `rightPorts = {1, 4, 6}`, `leftPorts = {1, 3, 5}`, etc.
  3. Iterate through every cell `(r, c)` in the grid.
  4. For each cell, check its neighbors in two directions (e.g., right and down) to avoid redundant checks.
     - **Check Right Neighbor**: If `c+1` is in bounds, get the street types `s1 = grid[r][c]` and `s2 = grid[r][c+1]`. If `s1` has a right port and `s2` has a left port, they are connected. Perform `union(r*n + c, r*n + c+1)`.
     - **Check Down Neighbor**: If `r+1` is in bounds, get street types `s1 = grid[r][c]` and `s2 = grid[r+1][c]`. If `s1` has a down port and `s2` has an up port, they are connected. Perform `union(r*n + c, (r+1)*n + c)`.
  5. After iterating through the entire grid, all connected cells will be in the same set.
  6. Check if the start cell `(0, 0)` and end cell `(m-1, n-1)` have the same root parent: `find(0) == find(m*n - 1)`. If they do, return `true`; otherwise, return `false`.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
private
  int[][] grid;
private
  int m;
private
  int n;
public
  boolean hasValidPath(int[][] grid) {
    this.grid = grid;
    m = grid.length;
    n = grid[0].length;
    p = new int[m * n];
    for (int i = 0; i < p.length; ++i) {
      p[i] = i;
    }
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int e = grid[i][j];
        if (e == 1) {
          left(i, j);
          right(i, j);
        } else if (e == 2) {
          up(i, j);
          down(i, j);
        } else if (e == 3) {
          left(i, j);
          down(i, j);
        } else if (e == 4) {
          right(i, j);
          down(i, j);
        } else if (e == 5) {
          left(i, j);
          up(i, j);
        } else {
          right(i, j);
          up(i, j);
        }
      }
    }
    return find(0) == find(m * n - 1);
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
private
  void left(int i, int j) {
    if (j > 0 &&
        (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {
      p[find(i * n + j)] = find(i * n + j - 1);
    }
  }
private
  void right(int i, int j) {
    if (j < n - 1 &&
        (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {
      p[find(i * n + j)] = find(i * n + j + 1);
    }
  }
private
  void up(int i, int j) {
    if (i > 0 &&
        (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {
      p[find(i * n + j)] = find((i - 1) * n + j);
    }
  }
private
  void down(int i, int j) {
    if (i < m - 1 &&
        (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {
      p[find(i * n + j)] = find((i + 1) * n + j);
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  bool hasValidPath(vector<vector<int>> &grid) {
    int m = grid.size();
    int n = grid[0].size();
    p.resize(m * n);
    for (int i = 0; i < p.size(); ++i)
      p[i] = i;
    auto left = [&](int i, int j) {
      if (j > 0 &&
          (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {
        p[find(i * n + j)] = find(i * n + j - 1);
      }
    };
    auto right = [&](int i, int j) {
      if (j < n - 1 &&
          (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {
        p[find(i * n + j)] = find(i * n + j + 1);
      }
    };
    auto up = [&](int i, int j) {
      if (i > 0 &&
          (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {
        p[find(i * n + j)] = find((i - 1) * n + j);
      }
    };
    auto down = [&](int i, int j) {
      if (i < m - 1 &&
          (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {
        p[find(i * n + j)] = find((i + 1) * n + j);
      }
    };
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int e = grid[i][j];
        if (e == 1) {
          left(i, j);
          right(i, j);
        } else if (e == 2) {
          up(i, j);
          down(i, j);
        } else if (e == 3) {
          left(i, j);
          down(i, j);
        } else if (e == 4) {
          right(i, j);
          down(i, j);
        } else if (e == 5) {
          left(i, j);
          up(i, j);
        } else {
          right(i, j);
          up(i, j);
        }
      }
    }
    return find(0) == find(m * n - 1);
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
};

```

### Python

```python
class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool: m, n = len(grid), len(grid[0]) p = list(range(m * n)) def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def left(i, j): if j > 0 and grid[i][j - 1] in (1, 4, 6): p[find(i * n + j)] = find(i * n + j - 1) def right(i, j): if j < n - 1 and grid[i][j + 1] in (1, 3, 5): p[find(i * n + j)] = find(i * n + j + 1) def up(i, j): if i > 0 and grid[i - 1][j] in (2, 3, 4): p[find(i * n + j)] = find((i - 1) * n + j) def down(i, j): if i < m - 1 and grid[i + 1][j] in (2, 5, 6): p[find(i * n + j)] = find((i + 1) * n + j) for i in range(m): for j in range(n): e = grid[i][j] if e == 1: left(i, j) right(i, j) elif e == 2: up(i, j) down(i, j) elif e == 3: left(i, j) down(i, j) elif e == 4: right(i, j) down(i, j) elif e == 5: left(i, j) up(i, j) else: right(i, j) up(i, j) return find(0) == find(m * n - 1)

```