Check if There is a Valid Path in a Grid

Med

#1289Time: 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`.1 company

Algorithms

Depth-First Search Breadth-First Search Union Find

Data structures

Array Matrix

Companies

Robinhood

Prompt

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.

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:

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:

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

3 approaches with complexity analysis and trade-offs.

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.

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).

Walkthrough

1class Solution {2    // directions[street_type - 1] = {{dr1, dc1}, {dr2, dc2}}3    private int[][][] directions = {4        {{0, -1}, {0, 1}},   // 1: left-right5        {{-1, 0}, {1, 0}},   // 2: up-down6        {{0, -1}, {1, 0}},   // 3: left-down7        {{0, 1}, {1, 0}},    // 4: right-down8        {{0, -1}, {-1, 0}},  // 5: left-up9        {{0, 1}, {-1, 0}}    // 6: right-up10    };11    private int m, n;12    private boolean[][] visited;13 14    public boolean hasValidPath(int[][] grid) {15        m = grid.length;16        n = grid[0].length;17        visited = new boolean[m][n];18        return dfs(0, 0, grid);19    }20 21    private boolean dfs(int r, int c, int[][] grid) {22        if (r == m - 1 && c == n - 1) {23            return true;24        }25        visited[r][c] = true;26 27        int streetType = grid[r][c];28        for (int[] dir : directions[streetType - 1]) {29            int nr = r + dir[0];30            int nc = c + dir[1];31 32            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {33                // Check if the next street connects back34                int nextStreetType = grid[nr][nc];35                for (int[] backDir : directions[nextStreetType - 1]) {36                    if (nr + backDir[0] == r && nc + backDir[1] == c) {37                        if (dfs(nr, nc, grid)) {38                            return true;39                        }40                    }41                }42            }43        }44        return false;45    }46}

Complexity

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`.

Trade-offs

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.

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.

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.

Walkthrough

1import java.util.LinkedList;2import java.util.Queue;3 4class Solution {5    public boolean hasValidPath(int[][] grid) {6        int m = grid.length;7        int n = grid[0].length;8 9        // directions[street_type - 1] = {{dr1, dc1}, {dr2, dc2}}10        int[][][] directions = {11            {{0, -1}, {0, 1}},   // 1: left-right12            {{-1, 0}, {1, 0}},   // 2: up-down13            {{0, -1}, {1, 0}},   // 3: left-down14            {{0, 1}, {1, 0}},    // 4: right-down15            {{0, -1}, {-1, 0}},  // 5: left-up16            {{0, 1}, {-1, 0}}    // 6: right-up17        };18 19        boolean[][] visited = new boolean[m][n];20        Queue<int[]> queue = new LinkedList<>();21 22        queue.offer(new int[]{0, 0});23        visited[0][0] = true;24 25        while (!queue.isEmpty()) {26            int[] curr = queue.poll();27            int r = curr[0];28            int c = curr[1];29 30            if (r == m - 1 && c == n - 1) {31                return true;32            }33 34            int streetType = grid[r][c];35            for (int[] dir : directions[streetType - 1]) {36                int nr = r + dir[0];37                int nc = c + dir[1];38 39                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {40                    int nextStreetType = grid[nr][nc];41                    // Check if the next street connects back to the current cell42                    for (int[] backDir : directions[nextStreetType - 1]) {43                        if (nr + backDir[0] == r && nc + backDir[1] == c) {44                            visited[nr][nc] = true;45                            queue.offer(new int[]{nr, nc});46                        }47                    }48                }49            }50        }51        return false;52    }53}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

1class Solution {2    class DSU {3        int[] parent;4        public DSU(int n) {5            parent = new int[n];6            for (int i = 0; i < n; i++) {7                parent[i] = i;8            }9        }10        public int find(int i) {11            if (parent[i] == i) {12                return i;13            }14            return parent[i] = find(parent[i]);15        }16        public void union(int i, int j) {17            int rootI = find(i);18            int rootJ = find(j);19            if (rootI != rootJ) {20                parent[rootI] = rootJ;21            }22        }23    }24 25    public boolean hasValidPath(int[][] grid) {26        int m = grid.length;27        int n = grid[0].length;28        29        // Ports: 0:up, 1:right, 2:down, 3:left30        int[][] ports = {31            {0, 0, 0, 0}, // dummy for 032            {0, 1, 0, 1}, // 1: right, left33            {1, 0, 1, 0}, // 2: up, down34            {0, 0, 1, 1}, // 3: down, left35            {0, 1, 1, 0}, // 4: right, down36            {1, 0, 0, 1}, // 5: up, left37            {1, 1, 0, 0}  // 6: up, right38        };39 40        DSU dsu = new DSU(m * n);41 42        for (int r = 0; r < m; r++) {43            for (int c = 0; c < n; c++) {44                int type = grid[r][c];45                int currentIdx = r * n + c;46 47                // Check connection down48                if (r + 1 < m) {49                    int downType = grid[r+1][c];50                    if (ports[type][2] == 1 && ports[downType][0] == 1) {51                        dsu.union(currentIdx, (r + 1) * n + c);52                    }53                }54                // Check connection right55                if (c + 1 < n) {56                    int rightType = grid[r][c+1];57                    if (ports[type][1] == 1 && ports[rightType][3] == 1) {58                        dsu.union(currentIdx, r * n + (c + 1));59                    }60                }61            }62        }63        64        return dsu.find(0) == dsu.find(m * n - 1);65    }66}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  int[] p;4private5  int[][] grid;6private7  int m;8private9  int n;10public11  boolean hasValidPath(int[][] grid) {12    this.grid = grid;13    m = grid.length;14    n = grid[0].length;15    p = new int[m * n];16    for (int i = 0; i < p.length; ++i) {17      p[i] = i;18    }19    for (int i = 0; i < m; ++i) {20      for (int j = 0; j < n; ++j) {21        int e = grid[i][j];22        if (e == 1) {23          left(i, j);24          right(i, j);25        } else if (e == 2) {26          up(i, j);27          down(i, j);28        } else if (e == 3) {29          left(i, j);30          down(i, j);31        } else if (e == 4) {32          right(i, j);33          down(i, j);34        } else if (e == 5) {35          left(i, j);36          up(i, j);37        } else {38          right(i, j);39          up(i, j);40        }41      }42    }43    return find(0) == find(m * n - 1);44  }45private46  int find(int x) {47    if (p[x] != x) {48      p[x] = find(p[x]);49    }50    return p[x];51  }52private53  void left(int i, int j) {54    if (j > 0 &&55        (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {56      p[find(i * n + j)] = find(i * n + j - 1);57    }58  }59private60  void right(int i, int j) {61    if (j < n - 1 &&62        (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {63      p[find(i * n + j)] = find(i * n + j + 1);64    }65  }66private67  void up(int i, int j) {68    if (i > 0 &&69        (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {70      p[find(i * n + j)] = find((i - 1) * n + j);71    }72  }73private74  void down(int i, int j) {75    if (i < m - 1 &&76        (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {77      p[find(i * n + j)] = find((i + 1) * n + j);78    }79  }80}

1class Solution {2public:3  vector<int> p;4  bool hasValidPath(vector<vector<int>> &grid) {5    int m = grid.size();6    int n = grid[0].size();7    p.resize(m * n);8    for (int i = 0; i < p.size(); ++i)9      p[i] = i;10    auto left = [&](int i, int j) {11      if (j > 0 &&12          (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {13        p[find(i * n + j)] = find(i * n + j - 1);14      }15    };16    auto right = [&](int i, int j) {17      if (j < n - 1 &&18          (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {19        p[find(i * n + j)] = find(i * n + j + 1);20      }21    };22    auto up = [&](int i, int j) {23      if (i > 0 &&24          (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {25        p[find(i * n + j)] = find((i - 1) * n + j);26      }27    };28    auto down = [&](int i, int j) {29      if (i < m - 1 &&30          (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {31        p[find(i * n + j)] = find((i + 1) * n + j);32      }33    };34    for (int i = 0; i < m; ++i) {35      for (int j = 0; j < n; ++j) {36        int e = grid[i][j];37        if (e == 1) {38          left(i, j);39          right(i, j);40        } else if (e == 2) {41          up(i, j);42          down(i, j);43        } else if (e == 3) {44          left(i, j);45          down(i, j);46        } else if (e == 4) {47          right(i, j);48          down(i, j);49        } else if (e == 5) {50          left(i, j);51          up(i, j);52        } else {53          right(i, j);54          up(i, j);55        }56      }57    }58    return find(0) == find(m * n - 1);59  }60  int find(int x) {61    if (p[x] != x)62      p[x] = find(p[x]);63    return p[x];64  }65};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  int[] p;4private5  int[][] grid;6private7  int m;8private9  int n;10public11  boolean hasValidPath(int[][] grid) {12    this.grid = grid;13    m = grid.length;14    n = grid[0].length;15    p = new int[m * n];16    for (int i = 0; i < p.length; ++i) {17      p[i] = i;18    }19    for (int i = 0; i < m; ++i) {20      for (int j = 0; j < n; ++j) {21        int e = grid[i][j];22        if (e == 1) {23          left(i, j);24          right(i, j);25        } else if (e == 2) {26          up(i, j);27          down(i, j);28        } else if (e == 3) {29          left(i, j);30          down(i, j);31        } else if (e == 4) {32          right(i, j);33          down(i, j);34        } else if (e == 5) {35          left(i, j);36          up(i, j);37        } else {38          right(i, j);39          up(i, j);40        }41      }42    }43    return find(0) == find(m * n - 1);44  }45private46  int find(int x) {47    if (p[x] != x) {48      p[x] = find(p[x]);49    }50    return p[x];51  }52private53  void left(int i, int j) {54    if (j > 0 &&55        (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {56      p[find(i * n + j)] = find(i * n + j - 1);57    }58  }59private60  void right(int i, int j) {61    if (j < n - 1 &&62        (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {63      p[find(i * n + j)] = find(i * n + j + 1);64    }65  }66private67  void up(int i, int j) {68    if (i > 0 &&69        (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {70      p[find(i * n + j)] = find((i - 1) * n + j);71    }72  }73private74  void down(int i, int j) {75    if (i < m - 1 &&76        (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {77      p[find(i * n + j)] = find((i + 1) * n + j);78    }79  }80}

1class Solution {2public:3  vector<int> p;4  bool hasValidPath(vector<vector<int>> &grid) {5    int m = grid.size();6    int n = grid[0].size();7    p.resize(m * n);8    for (int i = 0; i < p.size(); ++i)9      p[i] = i;10    auto left = [&](int i, int j) {11      if (j > 0 &&12          (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {13        p[find(i * n + j)] = find(i * n + j - 1);14      }15    };16    auto right = [&](int i, int j) {17      if (j < n - 1 &&18          (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {19        p[find(i * n + j)] = find(i * n + j + 1);20      }21    };22    auto up = [&](int i, int j) {23      if (i > 0 &&24          (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {25        p[find(i * n + j)] = find((i - 1) * n + j);26      }27    };28    auto down = [&](int i, int j) {29      if (i < m - 1 &&30          (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {31        p[find(i * n + j)] = find((i + 1) * n + j);32      }33    };34    for (int i = 0; i < m; ++i) {35      for (int j = 0; j < n; ++j) {36        int e = grid[i][j];37        if (e == 1) {38          left(i, j);39          right(i, j);40        } else if (e == 2) {41          up(i, j);42          down(i, j);43        } else if (e == 3) {44          left(i, j);45          down(i, j);46        } else if (e == 4) {47          right(i, j);48          down(i, j);49        } else if (e == 5) {50          left(i, j);51          up(i, j);52        } else {53          right(i, j);54          up(i, j);55        }56      }57    }58    return find(0) == find(m * n - 1);59  }60  int find(int x) {61    if (p[x] != x)62      p[x] = find(p[x]);63    return p[x];64  }65};

1class Solution:2    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)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.