Check if There is a Valid Path in a Grid — Solution
Check if There is a Valid Path in a Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Check if There is a Valid Path in a Grid is a medium coding problem on depth-first search, matrix and breadth-first search, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Matrix, Breadth-First Search, Union Find
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Every cell of an m x n grid holds one street piece, given as a number from 1 to 6:
1joins the left and right neighbours.2joins the upper and lower neighbours.3joins the left and lower neighbours.4joins the right and lower neighbours.5joins the left and upper neighbours.6joins the right and upper neighbours.
You may step from a cell to an adjacent one only if the street in your cell opens toward that neighbour and the neighbour's street opens back toward you. Streets cannot be rotated.
Starting at the top-left cell (0, 0), return true if the streets lead you to the bottom-right cell (m - 1, n - 1).
Example 1
Input: grid = [[4,1,3],[6,1,5]]
Output: true
Explanation: (0,0) opens right into the straight piece at (0,1), then (0,2) turns down into (1,2), which opens upward.
Example 2
Input: grid = [[1,2],[2,1]]
Output: false
Explanation: (0,0) opens only left and right, but (0,1) is a vertical piece that does not open to the left.
Example 3
Input: grid = [[5]]
Output: true
Explanation: The start is already the destination.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 3001 <= grid[i][j] <= 6
Hints for Check if There is a Valid Path in a Grid
Hint 1
Model each street type as the set of directions it opens toward.
Hint 2
A move between neighbours is allowed only when both cells open toward each other — check the neighbour for the opposite direction.
Hint 3
Run a BFS or DFS from (0, 0) using that rule and report whether (m − 1, n − 1) is visited.
How to solve Check if There is a Valid Path in a Grid
The grid is a graph whose edges exist only between neighbouring cells that open toward each other; the question is plain reachability from the top-left to the bottom-right.
Approach
- Encode each street type as a 4-bit mask of openings (up, right, down, left).
- BFS from
(0, 0). From cell(r, c)try every directiondits mask contains. - Move to the neighbour if it is inside the grid, unvisited, and its mask contains the opposite direction
(d + 2) mod 4. - Return
trueas soon as(m − 1, n − 1)is reached;falsewhen the queue empties.
Why it works
Two cells are connected by a usable street exactly when both openings face each other, so the mutual-opening test reproduces the street graph precisely. BFS visits every cell reachable in that graph, so the destination is reached if and only if a valid path exists.
Complexity
- Time —
O(m · n) - Space —
O(m · n)
Pitfalls
- Checking only the current cell's opening lets you walk into a piece that does not connect back.
- A 1 × 1 grid is trivially
true. - Paths may wind up and left as well as down and right — do not restrict the search to monotone moves.
Reference solution
Python
from typing import List
from collections import deque
def hasValidPath(grid: List[List[int]]) -> bool:
m, n = len(grid), len(grid[0])
masks = [0, 10, 5, 12, 6, 9, 3]
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
seen = [[False] * n for _ in range(m)]
seen[0][0] = True
q = deque([(0, 0)])
while q:
r, c = q.popleft()
if r == m - 1 and c == n - 1:
return True
mk = masks[grid[r][c]]
for d in range(4):
if not (mk >> d) & 1:
continue
nr, nc = r + dr[d], c + dc[d]
if nr < 0 or nr >= m or nc < 0 or nc >= n or seen[nr][nc]:
continue
if not (masks[grid[nr][nc]] >> ((d + 2) % 4)) & 1:
continue
seen[nr][nc] = True
q.append((nr, nc))
return FalseJava
public static boolean hasValidPath(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] masks = {0, 10, 5, 12, 6, 9, 3};
int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
boolean[] seen = new boolean[m * n];
int[] queue = new int[m * n];
int head = 0, tail = 0;
queue[tail++] = 0;
seen[0] = true;
while (head < tail) {
int id = queue[head++];
int r = id / n, c = id % n;
if (r == m - 1 && c == n - 1) return true;
int mk = masks[grid[r][c]];
for (int d = 0; d < 4; d++) {
if ((mk & (1 << d)) == 0) continue;
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if ((masks[grid[nr][nc]] & (1 << ((d + 2) % 4))) == 0) continue;
int nid = nr * n + nc;
if (!seen[nid]) { seen[nid] = true; queue[tail++] = nid; }
}
}
return false;
}C++
bool hasValidPath(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int masks[7] = {0, 10, 5, 12, 6, 9, 3};
int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
vector<char> seen(m * n, 0);
vector<int> queue;
queue.push_back(0);
seen[0] = 1;
for (size_t h = 0; h < queue.size(); h++) {
int r = queue[h] / n, c = queue[h] % n;
if (r == m - 1 && c == n - 1) return true;
int mk = masks[grid[r][c]];
for (int d = 0; d < 4; d++) {
if ((mk & (1 << d)) == 0) continue;
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if ((masks[grid[nr][nc]] & (1 << ((d + 2) % 4))) == 0) continue;
int nid = nr * n + nc;
if (!seen[nid]) { seen[nid] = 1; queue.push_back(nid); }
}
}
return false;
}JavaScript
var hasValidPath = function(grid) {
var m = grid.length, n = grid[0].length;
var masks = [0, 10, 5, 12, 6, 9, 3];
var dr = [-1, 0, 1, 0], dc = [0, 1, 0, -1];
var seen = [];
for (var i = 0; i < m * n; i++) seen.push(false);
var queue = [0];
seen[0] = true;
for (var h = 0; h < queue.length; h++) {
var r = Math.floor(queue[h] / n), c = queue[h] % n;
if (r === m - 1 && c === n - 1) return true;
var mk = masks[grid[r][c]];
for (var d = 0; d < 4; d++) {
if ((mk & (1 << d)) === 0) continue;
var nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if ((masks[grid[nr][nc]] & (1 << ((d + 2) % 4))) === 0) continue;
var id = nr * n + nc;
if (!seen[id]) { seen[id] = true; queue.push(id); }
}
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Matrix and Grid Traversal