Watch 7 video solutions for Check if There is a Valid Path in a Grid, a medium level problem involving Array, Depth-First Search, Breadth-First Search. This walkthrough by Xinru Chen has 1,900 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.lengthn == grid[i].length1 <= m, n <= 3001 <= grid[i][j] <= 6Problem 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 | 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 |