How hard is LeetCode 1391. Check if There is a Valid Path in a Grid?

LeetCode 1391. Check if There is a Valid Path in a Grid is rated Medium on LeetCode.

What is the time complexity of LeetCode 1391. Check if There is a Valid Path in a Grid?

The Python solution on this page runs in O(V+E).

What is the space complexity of LeetCode 1391. Check if There is a Valid Path in a Grid?

The Python solution on this page uses O(V) auxiliary space.

What topics does LeetCode 1391. Check if There is a Valid Path in a Grid cover?

LeetCode 1391. Check if There is a Valid Path in a Grid is tagged Depth-First Search, Breadth-First Search, Union Find, Array and Matrix on LeetCode.

Check if There is a Valid Path in a Grid — LeetCode 1391 Python Solution

MediumDepth-First SearchBreadth-First SearchUnion FindArrayMatrix

Problem: #1391
Pattern: Union-Find
Reading time: 8 min
Source: leetcode.com

The problem

You are given an m x n grid. Each cell of grid represents a street.

Example

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).

Python solution

Python

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)

Complexity

Measure	Complexity
Time	O(V+E)
Space	O(V) auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1391. Check if There is a Valid Path in a Grid is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1391. Check if There is a Valid Path in a Grid?: LeetCode 1391. Check if There is a Valid Path in a Grid is rated Medium on LeetCode.
What is the time complexity of LeetCode 1391. Check if There is a Valid Path in a Grid?: The Python solution on this page runs in O(V+E).
What is the space complexity of LeetCode 1391. Check if There is a Valid Path in a Grid?: The Python solution on this page uses O(V) auxiliary space.
What topics does LeetCode 1391. Check if There is a Valid Path in a Grid cover?: LeetCode 1391. Check if There is a Valid Path in a Grid is tagged Depth-First Search, Breadth-First Search, Union Find, Array and Matrix on LeetCode.