#1391

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Check if There is a Valid Path in a Grid

Check if there is a valid path from the upper-left to the bottom-right corner of a grid using depth-first search.

array depth first search breadth first search union find matrix

Problem Statement

You are given a grid of size m x n, where each cell represents a street with a specific number indicating its connection type. The goal is to determine if there exists a valid path from the top-left corner (0, 0) to the bottom-right corner (m - 1, n - 1) following the grid's street connections.

The streets are represented by integers, and each number specifies which directions you can move to another cell. Valid movements are based on specific rules where you must follow the correct path based on the street number at each cell. You must return true if a valid path exists; otherwise, return false.

Examples

Example 1

Input: grid = [[2,4,3],[6,5,2]]

Output: true

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

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

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

Solution Approach

Depth-First Search (DFS)

A DFS can be implemented to explore all possible paths from the top-left cell. By visiting each cell and checking its connected street type, you can determine if it is possible to move through the grid to reach the bottom-right corner. Use a stack to keep track of the current position and its valid moves.

Backtracking

Backtracking can be employed to explore paths. If a path reaches a dead-end, backtrack and try a different route. Ensure each cell is visited only once to avoid infinite loops and redundant calculations.

Breadth-First Search (BFS)

Alternatively, BFS can be used to explore the grid level by level. This ensures that you check all reachable cells from the starting position before moving deeper. BFS is often more efficient for this type of problem since it explores all options systematically.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depend on the approach chosen. For DFS, the time complexity is O(m * n), as you might need to visit every cell in the grid. Space complexity is also O(m * n) due to the stack or queue used in DFS or BFS. The space complexity can be reduced by using iterative methods.

What Interviewers Usually Probe

Look for correct implementation of DFS or BFS to explore the grid.
Pay attention to how the candidate handles edge cases like unreachable cells or circular paths.
Check if the candidate optimizes their algorithm to avoid unnecessary exploration of already visited cells.

Common Pitfalls or Variants

Common pitfalls

Forgetting to mark visited cells, leading to infinite loops or revisiting cells unnecessarily.
Not correctly managing the street connection rules, resulting in invalid moves and incorrect results.
Overcomplicating the solution by not simplifying the pathfinding logic.

Follow-up variants

Increase grid size to test scalability with larger m and n values.
Introduce more complex street connection rules and validate the pathfinding ability.
Modify the grid to have isolated regions, testing how the algorithm handles disconnected paths.

FAQ

What is the most efficient way to solve 'Check if There is a Valid Path in a Grid'?

The most efficient way to solve this problem is by using Depth-First Search (DFS) or Breadth-First Search (BFS) with careful attention to handling grid boundaries and valid moves.

How do I handle revisiting cells in this problem?

To avoid revisiting cells, mark each cell as visited before exploring adjacent cells, ensuring that you do not revisit or get stuck in infinite loops.

What edge cases should I consider for this problem?

Edge cases include grids where no valid path exists, grids with isolated cells, and grids where the start or end cell cannot connect to the next cell.

How does DFS work in 'Check if There is a Valid Path in a Grid'?

DFS explores all possible paths from the starting cell by recursively visiting adjacent cells, checking if each move is valid based on the street type and connection rules.

What should I do if a path leads to a dead-end?

If a path leads to a dead-end, backtrack by returning to the previous cell and trying another valid direction until a solution is found or all options are exhausted.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        p = list(range(m * n))

        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        def left(i, j):
            if j > 0 and grid[i][j - 1] in (1, 4, 6):
                p[find(i * n + j)] = find(i * n + j - 1)

        def right(i, j):
            if j < n - 1 and grid[i][j + 1] in (1, 3, 5):
                p[find(i * n + j)] = find(i * n + j + 1)

        def up(i, j):
            if i > 0 and grid[i - 1][j] in (2, 3, 4):
                p[find(i * n + j)] = find((i - 1) * n + j)

        def down(i, j):
            if i < m - 1 and grid[i + 1][j] in (2, 5, 6):
                p[find(i * n + j)] = find((i + 1) * n + j)

        for i in range(m):
            for j in range(n):
                e = grid[i][j]
                if e == 1:
                    left(i, j)
                    right(i, j)
                elif e == 2:
                    up(i, j)
                    down(i, j)
                elif e == 3:
                    left(i, j)
                    down(i, j)
                elif e == 4:
                    right(i, j)
                    down(i, j)
                elif e == 5:
                    left(i, j)
                    up(i, j)
                else:
                    right(i, j)
                    up(i, j)
        return find(0) == find(m * n - 1)

Continue Practicing

#1267 count servers that communicate #1254 number of closed islands #1559 detect cycles in 2d grid