MediumNo. 1391
Check if There is a Valid Path in a Grid — LeetCode 1391 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Array, Matrix
- 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
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
- Time
- O(V+E)
- Space · auxiliary
- O(V)
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0130 | Surrounded Regions | Medium |
| 0200 | Number of Islands | Medium |
| 0695 | Max Area of Island | Medium |
| 0827 | Making A Large Island | Hard |
| 1020 | Number of Enclaves | Medium |
| 1254 | Number of Closed Islands | Medium |
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.