Check if There is a Valid Path in a Grid solution and explanation
Google
9 more videos on this problem
Check if There is a Valid Path in a Grid | Simplified to Easy | Leetcode 1391 | codestorywithMIKcodestorywithMIK · 23:05 · 7K views
Leetcode 1391. Check if There is a Valid Path in a GridElite Code · 28:50 · 1K views
1391. Check if There is a Valid Path in a Grid | Leetcode Daily - PythonLeetcode Daily · 7:31 · 343 views
Check if There is a Valid Path in a Grid | LeetCode 1391 - Pythonimpoldev · 8:18 · 288 views
Check if There is a Valid Path in a Grid | LeetCode 1391 🔥 | Graph + BFS Explained Study Placement · 23:51 · 120 views
Check if There is a Valid Path in a Grid | LeetCode 1391Streak To Scale · 7:40 · 101 views
Leetcode 1391. Check if There is a Valid Path in a Grid (BFS)Madhumitha Kolkar · 17:07 · 65 views
POTD Leetcode 1391. Check if There is a Valid Path in a Gridhowtocode online · 6:28 · 41 views
leetcode 1391 Check if There is a Valid Path in a Grid | DFSCode-Yao · 10:12 · 38 views
Check if There is a Valid Path in a Grid | LeetCode 1391 | POTD | Basic To Optimal | DSADCode Thought · 36:30 · 37 views
The problem
You are given an m x n grid. Each cell of grid represents a street. The street of grid[i][j] can be:
1which means a street connecting the left cell and the right cell.2which means a street connecting the upper cell and the lower cell.3which means a street connecting the left cell and the lower cell.4which means a street connecting the right cell and the lower cell.5which means a street connecting the left cell and the upper cell.6which 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.lengthn == grid[i].length1 <= m, n <= 3001 <= grid[i][j] <= 6
Approach overview
Problem Overview: You are given an m x n grid where each cell represents a street type connecting specific directions. The goal is to determine whether you can travel from the top-left cell to the bottom-right cell while following valid street connections between adjacent cells.
Approach 1: Breadth-First Search (BFS) Traversal (Time: O(m*n), Space: O(m*n))
Treat the grid as a graph where each cell is a node and edges exist only when two adjacent street types connect properly. Start from (0,0) and perform a BFS using a queue. For each cell, check the allowed movement directions based on its street type, then verify the neighboring cell also connects back to the current cell. Maintain a visited matrix to avoid reprocessing cells. BFS works well because you explore all reachable cells level by level and stop early once the bottom-right cell is reached.
Approach 2: Depth-First Search (DFS) Traversal (Time: O(m*n), Space: O(m*n))
DFS follows the same connectivity rules but explores paths recursively. From the current cell, attempt all valid directions allowed by the street type. Before moving, confirm the neighbor’s street allows entry from the opposite direction. Mark cells as visited to prevent cycles. DFS is straightforward to implement with recursion and works well for grid connectivity problems where the goal is simply determining reachability.
Approach 3: Union Find (Disjoint Set) (Time: O(m*n * α(m*n)), Space: O(m*n))
Model each grid cell as a node in a disjoint set structure. For every adjacent pair of cells, union them if their street types connect correctly. After processing the grid, check whether the start cell and end cell belong to the same set. This approach converts the traversal problem into a connectivity query. While slightly more complex to implement, it demonstrates strong understanding of graph connectivity structures.
Recommended for interviews: BFS or DFS is usually expected. Both clearly model the grid as a graph and validate directional connections between cells. BFS tends to be the most intuitive because it mirrors standard grid traversal patterns commonly used in breadth-first search problems. Understanding how street types restrict movement is the key insight. This problem also overlaps with concepts from depth-first search, array traversal, and matrix graph modeling.
Approach 1: Breadth-First Search (BFS)
The BFS approach involves using a queue to explore cells level by level. The idea is to start from the top-left corner and explore each connected component, following the constraints of the streets on the grid. We keep track of visited cells to avoid cycles as we traverse the grid. The queue helps in checking all possible neighbors for each cell, and the goal is to see if we can reach the bottom-right corner.
from collections import deque
def has_valid_path(grid):
m, n = len(grid), len(grid[0])
directions = {
1: [(0, -1), (0, 1)],
2: [(-1, 0), (1, 0)],
3: [(0, -1), (1, 0)],
4: [(0, 1), (1, 0)],
5: [(0, -1), (-1, 0)],
6: [(0, 1), (-1, 0)]
}
def in_bounds(x, y):
return 0 <= x < m and 0 <= y < n
queue = deque([(0, 0)])
visited = set((0, 0))
while queue:
x, y = queue.popleft()
if (x, y) == (m-1, n-1):
return True
for dx, dy in directions[grid[x][y]]:
nx, ny = x + dx, y + dy
if in_bounds(nx, ny) and (nx, ny) not in visited and (-dx, -dy) in directions[grid[nx][ny]]:
visited.add((nx, ny))
queue.append((nx, ny))
return Falseimport java.util.*;
public boolean hasValidPath(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][][] directions = {
{{0, -1}, {0, 1}}, // 1
{{-1, 0}, {1, 0}}, // 2
{{0, -1}, {1, 0}}, // 3
{{0, 1}, {1, 0}}, // 4
{{0, -1}, {-1, 0}},// 5
{{0, 1}, {-1, 0}} // 6
};
Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[m][n];
queue.add(new int[]{0, 0});
visited[0][0] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0], y = current[1];
if (x == m - 1 && y == n - 1) {
return true;
}
for (int[] d : directions[grid[x][y] - 1]) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
for (int[] backward : directions[grid[nx][ny] - 1]) {
if (nx + backward[0] == x && ny + backward[1] == y) {
queue.add(new int[]{nx, ny});
visited[nx][ny] = true;
break;
}
}
}
}
}
return false;
}The solution uses a queue for BFS to explore the grid starting from (0, 0). At each cell, it checks valid moves based on the current street type and explores connected components. If we reach the bottom-right cell, the function returns true.
Time Complexity: O(m * n), because each cell is visited at most once.
Space Complexity: O(m * n), for the visited set and the queue.
Approach 2: Depth-First Search (DFS)
The Depth-First Search (DFS) approach involves recursive exploration of each path starting from the top-left corner. For every cell, based on its street type, we explore all possible connected directions. Recursive backtracking helps explore each path completely before marking it as visited. The idea is to check if it is possible to reach the bottom-right corner using valid paths as per street constraints.
#include <vector>
using namespace std;
bool dfs(int x, int y, vector<vector<int>>& grid, vector<vector<bool>>& visited) {
if (x == grid.size() - 1 && y == grid[0].size() - 1) {
return true;
}
static const vector<vector<int>> directions[] = {
{{0, -1}, {0, 1}},
{{-1, 0}, {1, 0}},
{{0, -1}, {1, 0}},
{{0, 1}, {1, 0}},
{{0, -1}, {-1, 0}},
{{0, 1}, {-1, 0}}
};
visited[x][y] = true;
for (const auto& d : directions[grid[x][y] - 1]) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && !visited[nx][ny]) {
for (const auto& back : directions[grid[nx][ny] - 1]) {
if (nx + back[0] == x && ny + back[1] == y) {
if (dfs(nx, ny, grid, visited)) {
return true;
}
}
}
}
}
return false;
}
bool hasValidPath(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) {
return false;
}
vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
return dfs(0, 0, grid, visited);
}function dfs(x, y, grid, visited) {
if (x === grid.length - 1 && y === grid[0].length - 1) {
return true;
}
const directions = [
[[0, -1], [0, 1]],
[[-1, 0], [1, 0]],
[[0, -1], [1, 0]],
[[0, 1], [1, 0]],
[[0, -1], [-1, 0]],
[[0, 1], [-1, 0]]
];
visited[x][y] = true;
for (let [dx, dy] of directions[grid[x][y] - 1]) {
const nx = x + dx, ny = y + dy;
if (
nx >= 0 &&
nx < grid.length &&
ny >= 0 &&
ny < grid[0].length &&
!visited[nx][ny]
) {
for (let [rdx, rdy] of directions[grid[nx][ny] - 1]) {
if (nx + rdx === x && ny + rdy === y) {
if (dfs(nx, ny, grid, visited)) return true;
}
}
}
}
return false;
}
function hasValidPath(grid) {
if (!grid.length || !grid[0].length) return false;
const visited = Array.from({ length: grid.length }, () => Array(grid[0].length).fill(false));
return dfs(0, 0, grid, visited);
}This C++ solution uses recursive DFS to explore potential paths from each cell based on the street type. It uses backtracking to continue exploring the grid until the target cell is found or all paths are exhausted.
Time Complexity: O(m * n), for visiting every cell once recursively in the worst case.
Space Complexity: O(m * n), due to the recursive call stack and the visited map.
Approach 3: Default Approach
func hasValidPath(grid [][]int) bool {
m, n := len(grid), len(grid[0])
p := make([]int, m*n)
for i := range p {
p[i] = i
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
left := func(i, j int) {
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)
}
}
right := func(i, j int) {
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)
}
}
up := func(i, j int) {
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)
}
}
down := func(i, j int) {
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 i, row := range grid {
for j, e := range row {
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)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) | Time Complexity: O(m * n), because each cell is visited at most once. |
| Depth-First Search (DFS) | Time Complexity: O(m * n), for visiting every cell once recursively in the worst case. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(m*n) | O(m*n) | Best general solution for grid traversal and shortest reachability checks |
| Depth-First Search (DFS) | O(m*n) | O(m*n) | Simple recursive implementation when only reachability matters |
| Union Find (Disjoint Set) | O(m*n * α(m*n)) | O(m*n) | Useful when modeling connectivity or solving multiple connectivity queries |
Frequently asked questions
Is Check if There is a Valid Path in a Grid easy or hard?
The problem is rated Medium because the traversal itself is straightforward, but the directional constraints between street types add complexity. Correctly validating bidirectional connections between cells is the main challenge.
Check if There is a Valid Path in a Grid Python/Java solution
Python and Java implementations usually use BFS with a queue. Each street type maps to specific movement directions, and before moving to a neighbor the algorithm verifies the neighbor connects back to the current cell. The full traversal completes in O(m*n) time.
How to solve Check if There is a Valid Path in a Grid in O(m*n)?
Use BFS or DFS starting from the top-left cell. For each cell, check which directions are allowed by its street type, then verify the neighboring cell allows entry from the opposite direction. Continue traversal while marking cells as visited. If the bottom-right cell is reached, a valid path exists.
What is the best approach for Check if There is a Valid Path in a Grid?
Breadth-First Search (BFS) is typically the best approach. Treat the grid as a graph where each street type defines valid movement directions. BFS explores reachable cells while verifying that neighboring streets connect correctly in both directions. The algorithm runs in O(m*n) time and uses O(m*n) space for the visited structure.
Is Check if There is a Valid Path in a Grid asked at Google/Amazon/Meta?
Grid traversal and graph connectivity problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The problem tests understanding of BFS/DFS traversal, direction validation, and modeling a matrix as a graph.
What data structure is used in Check if There is a Valid Path in a Grid?
The core data structures are a queue for BFS or recursion stack for DFS, along with a visited matrix to avoid revisiting cells. Some implementations also use direction maps to represent valid street connections between adjacent cells.
What is the time complexity of Check if There is a Valid Path in a Grid?
The optimal BFS or DFS solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is visited at most once, and only a constant number of direction checks are performed per cell. The space complexity is also O(m*n) due to the visited matrix or recursion stack.