Path With Minimum Effort — LeetCode 1631 Python Solution
MediumDepth-First SearchBreadth-First SearchUnion FindArrayBinary SearchMatrixHeap (Priority Queue)
- Problem
- #1631
- Pattern
- Union-Find
- 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
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
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
| Measure | Complexity |
|---|---|
| Time | O(m \times n \times \log(m \times n)) |
| Space | O(m \times n) auxiliary |
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
LeetCode 778Swim in Rising WaterHardLeetCode 1970Last Day Where You Can Still CrossHardLeetCode 2812Find the Safest Path in a GridMediumLeetCode 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 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 \times n \times \log(m \times n)).
- What is the space complexity of LeetCode 1631. Path With Minimum Effort?
- The Python solution on this page uses O(m \times 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.