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

In this guide, you will get 1391. Check if There is a Valid Path in a Grid LeetCode Solution with the best time and space complexity. The solution to Check if There is a Valid Path in a Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Check if There is a Valid Path in a Grid solution in C++
Check if There is a Valid Path in a Grid solution in Java
Check if There is a Valid Path in a Grid solution in Python
Additional Resources

1391. Check if There is a Valid Path in a Grid LeetCode Solution image

Problem Statement of Check if There is a Valid Path in a Grid

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

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

1391. Check if There is a Valid Path in a Grid LeetCode Solution in C++

class Solution {
 public:
  bool hasValidPath(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    // g := upscaled grid
    vector<vector<bool>> g(m * 3, vector<bool>(n * 3));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        switch (grid[i][j]) {
          case 1:
            g[i * 3 + 1][j * 3 + 0] = true;
            g[i * 3 + 1][j * 3 + 1] = true;
            g[i * 3 + 1][j * 3 + 2] = true;
            break;
          case 2:
            g[i * 3 + 0][j * 3 + 1] = true;
            g[i * 3 + 1][j * 3 + 1] = true;
            g[i * 3 + 2][j * 3 + 1] = true;
            break;
          case 3:
            g[i * 3 + 1][j * 3 + 0] = true;
            g[i * 3 + 1][j * 3 + 1] = true;
            g[i * 3 + 2][j * 3 + 1] = true;
            break;
          case 4:
            g[i * 3 + 1][j * 3 + 1] = true;
            g[i * 3 + 1][j * 3 + 2] = true;
            g[i * 3 + 2][j * 3 + 1] = true;
            break;
          case 5:
            g[i * 3 + 0][j * 3 + 1] = true;
            g[i * 3 + 1][j * 3 + 0] = true;
            g[i * 3 + 1][j * 3 + 1] = true;
            break;
          case 6:
            g[i * 3 + 0][j * 3 + 1] = true;
            g[i * 3 + 1][j * 3 + 1] = true;
            g[i * 3 + 1][j * 3 + 2] = true;
            break;
        }

    return dfs(g, 1, 1);
  }

 private:
  bool dfs(vector<vector<bool>>& g, int i, int j) {
    if (i < 0 || i == g.size() || j < 0 || j == g[0].size())
      return false;
    if (!g[i][j])  // There's no path here.
      return false;
    if (i == g.size() - 2 && j == g[0].size() - 2)
      return true;

    g[i][j] = false;  // Mark as visited.
    return dfs(g, i + 1, j) || dfs(g, i - 1, j) || dfs(g, i, j + 1) ||
           dfs(g, i, j - 1);
  }
};
/* code provided by PROGIEZ */

1391. Check if There is a Valid Path in a Grid LeetCode Solution in Java

class Solution {
  public boolean hasValidPath(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    // g := upscaled grid
    boolean[][] g = new boolean[m * 3][n * 3];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        switch (grid[i][j]) {
          case 1:
            g[i * 3 + 1][j * 3 + 0] = true;
            g[i * 3 + 1][j * 3 + 1] = true;
            g[i * 3 + 1][j * 3 + 2] = true;
            break;
          case 2:
            g[i * 3 + 0][j * 3 + 1] = true;
            g[i * 3 + 1][j * 3 + 1] = true;
            g[i * 3 + 2][j * 3 + 1] = true;
            break;
          case 3:
            g[i * 3 + 1][j * 3 + 0] = true;
            g[i * 3 + 1][j * 3 + 1] = true;
            g[i * 3 + 2][j * 3 + 1] = true;
            break;
          case 4:
            g[i * 3 + 1][j * 3 + 1] = true;
            g[i * 3 + 1][j * 3 + 2] = true;
            g[i * 3 + 2][j * 3 + 1] = true;
            break;
          case 5:
            g[i * 3 + 0][j * 3 + 1] = true;
            g[i * 3 + 1][j * 3 + 0] = true;
            g[i * 3 + 1][j * 3 + 1] = true;
            break;
          case 6:
            g[i * 3 + 0][j * 3 + 1] = true;
            g[i * 3 + 1][j * 3 + 1] = true;
            g[i * 3 + 1][j * 3 + 2] = true;
            break;
        }

    return dfs(g, 1, 1);
  }

  private boolean dfs(boolean[][] g, int i, int j) {
    if (i < 0 || i == g.length || j < 0 || j == g[0].length)
      return false;
    if (!g[i][j]) // There's no path here.
      return false;
    if (i == g.length - 2 && j == g[0].length - 2)
      return true;

    g[i][j] = false; // Mark as visited.
    return dfs(g, i + 1, j) || dfs(g, i - 1, j) || dfs(g, i, j + 1) || dfs(g, i, j - 1);
  }
}
// code provided by PROGIEZ