Find the Safest Path in a Grid — LeetCode 2812 Python Solution
MediumBreadth-First SearchUnion FindArrayBinary SearchMatrixHeap (Priority Queue)
- Problem
- #2812
- Pattern
- Union-Find
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(n^2 \times \log n) |
| Space | O(1) auxiliary |
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
LeetCode 778Swim in Rising WaterHardLeetCode 1631Path With Minimum EffortMediumLeetCode 1970Last Day Where You Can Still CrossHardLeetCode 378Kth Smallest Element in a Sorted MatrixMediumLeetCode 1337The K Weakest Rows in a MatrixEasyLeetCode 1439Find the Kth Smallest Sum of a Matrix With Sorted RowsHard
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(n^2 \times \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.