Skip to main content
Talentd

Check if There is a Valid Path in a Grid - Solution & Explanation

MediumArrayDepth-First SearchBreadth-First SearchUnion Find12 min readAsked at: Samsung, Robinhood, Google
Practice this problem

Problem Statement

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

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.

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

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.

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.

Code

C++JavaScript

C++

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS)

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.

Depth-First Search (DFS)

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

Check if There is a Valid Path in a Grid | Simplified to Easy | Leetcode 1391 | codestorywithMIK • codestorywithMIK • 7,936 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Check if There is a Valid Path in a Grid with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if There Is a Valid Parentheses String Path