MediumNo. 2812
Find the Safest Path in a Grid — LeetCode 2812 Python Solution
- Pattern
- Union-Find
- Topics
- Breadth-First Search, Union Find, Array, Binary Search, Matrix, Heap (Priority Queue)
- Reading time
- 10 min
- Source
- leetcode.com
The problem
You are given a 0-indexed 2D matrix grid of size n x n, where (r, c) represents: A cell containing a thief if grid[r][c] = 1 An empty cell if grid[r][c] = 0 You are initially positioned at cell (0, 0). In one move, you can move to any adjacent cell in the grid, including cells containing thieves.
Example
- Input
- grid = [[1,0,0],[0,0,0],[0,0,1]]
- Output
- 0
- Explanation
- All paths from (0, 0) to (n - 1, n - 1) go through the thieves in cells (0, 0) and (n - 1, n - 1).
Python solution
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
class Solution:
def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
n = len(grid)
if grid[0][0] or grid[n - 1][n - 1]:
return 0
q = deque()
dist = [[inf] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if grid[i][j]:
q.append((i, j))
dist[i][j] = 0
dirs = (-1, 0, 1, 0, -1)
while q:
i, j = q.popleft()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n and dist[x][y] == inf:
dist[x][y] = dist[i][j] + 1
q.append((x, y))
q = ((dist[i][j], i, j) for i in range(n) for j in range(n))
q = sorted(q, reverse=True)
uf = UnionFind(n * n)
for d, i, j in q:
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n and dist[x][y] >= d:
uf.union(i * n + j, x * n + y)
if uf.find(0) == uf.find(n * n - 1):
return int(d)
return 0Complexity
- Time
- O(n2 × log n)
- Space · auxiliary
- O(1)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2812. Find the Safest 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 |
|---|---|---|
| 0778 | Swim in Rising Water | Hard |
| 1631 | Path With Minimum Effort | Medium |
| 1970 | Last Day Where You Can Still Cross | Hard |
| 0378 | Kth Smallest Element in a Sorted Matrix | Medium |
| 1337 | The K Weakest Rows in a Matrix | Easy |
| 1439 | Find the Kth Smallest Sum of a Matrix With Sorted Rows | Hard |
Frequently asked questions
- How hard is LeetCode 2812. Find the Safest Path in a Grid?
LeetCode 2812. Find the Safest Path in a Grid is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2812. Find the Safest Path in a Grid?
The Python solution on this page runs in O(n2 × log n).
- What is the space complexity of LeetCode 2812. Find the Safest Path in a Grid?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2812. Find the Safest Path in a Grid cover?
LeetCode 2812. Find the Safest Path in a Grid is tagged Breadth-First Search, Union Find, Array, Binary Search, Matrix and Heap (Priority Queue) on LeetCode.