MediumNo. 1631
Path With Minimum Effort — LeetCode 1631 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Array, Binary Search, Matrix, Heap (Priority Queue)
- Reading time
- 8 min
- Source
- leetcode.com
The problem
You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col).
Example
- Input
- heights = [[1,2,2],[3,8,2],[5,3,5]]
- Output
- 2
- Explanation
- The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
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
def connected(self, a, b):
return self.find(a) == self.find(b)
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
m, n = len(heights), len(heights[0])
uf = UnionFind(m * n)
e = []
dirs = (0, 1, 0)
for i in range(m):
for j in range(n):
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n:
e.append(
(abs(heights[i][j] - heights[x][y]), i * n + j, x * n + y)
)
e.sort()
for h, a, b in e:
uf.union(a, b)
if uf.connected(0, m * n - 1):
return h
return 0Complexity
- Time
- O(m × n × log(m × n))
- Space · auxiliary
- O(m × n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1631. Path With Minimum Effort 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 |
| 1970 | Last Day Where You Can Still Cross | Hard |
| 2812 | Find the Safest Path in a Grid | Medium |
| 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 1631. Path With Minimum Effort?
LeetCode 1631. Path With Minimum Effort is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1631. Path With Minimum Effort?
The Python solution on this page runs in O(m × n × log(m × n)).
- What is the space complexity of LeetCode 1631. Path With Minimum Effort?
The Python solution on this page uses O(m × n) auxiliary space.
- What topics does LeetCode 1631. Path With Minimum Effort cover?
LeetCode 1631. Path With Minimum Effort is tagged Depth-First Search, Breadth-First Search, Union Find, Array, Binary Search, Matrix and Heap (Priority Queue) on LeetCode.