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.
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.
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.
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.
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.
C++
JavaScript
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 | 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 | — |
| 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 |
LeetCode1391. Check Valid Path - BFS • Xinru Chen • 1,900 views views
Watch 6 more video solutions →Practice Check if There is a Valid Path in a Grid with our built-in code editor and test cases.
Practice on FleetCode