Scale Engineer

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 SearchBreadth-First SearchUnion Find
Data structures
ArrayMatrix
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

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;    }}

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.

Solutions

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);    }  }}

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 →

Next problem