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). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.
A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.
Return the minimum effort required to travel from the top-left cell to the bottom-right cell.
Example 1:
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. This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.
Example 2:
Input: heights = [[1,2,3],[3,8,4],[5,3,5]] Output: 1 Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].
Example 3:
Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]] Output: 0 Explanation: This route does not require any effort.
Constraints:
rows == heights.lengthcolumns == heights[i].length1 <= rows, columns <= 1001 <= heights[i][j] <= 106
Union find or Binary search + BFS.
Union find:
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
m, n = len(heights), len(heights[0])
p = list(range(m * n))
e = []
for i in range(m):
for j in range(n):
if i < m - 1:
e.append((abs(heights[i][j] - heights[i + 1][j]), i * n + j, (i + 1) * n + j))
if j < n - 1:
e.append((abs(heights[i][j] - heights[i][j + 1]), i * n + j, i * n + j + 1))
e.sort()
for h, i, j in e:
p[find(i)] = find(j)
if find(0) == find(m * n - 1):
return h
return 0Binary search + BFS:
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
m, n = len(heights), len(heights[0])
left, right = 0, 999999
while left < right:
mid = (left + right) >> 1
q = deque([(0, 0)])
vis = set([(0, 0)])
while q:
i, j = q.popleft()
for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and (x, y) not in vis and abs(heights[i][j] - heights[x][y]) <= mid:
q.append((x, y))
vis.add((x, y))
if (m - 1, n - 1) in vis:
right = mid
else:
left = mid + 1
return leftUnion find:
class Solution {
private int[] p;
public int minimumEffortPath(int[][] heights) {
int m = heights.length;
int n = heights[0].length;
p = new int[m * n];
for (int i = 0; i < p.length; ++i) {
p[i] = i;
}
List<int[]> edges = new ArrayList<>();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i < m - 1) {
edges.add(new int[]{Math.abs(heights[i][j] - heights[i + 1][j]), i * n + j, (i + 1) * n + j});
}
if (j < n - 1) {
edges.add(new int[]{Math.abs(heights[i][j] - heights[i][j + 1]), i * n + j, i * n + j + 1});
}
}
}
Collections.sort(edges, Comparator.comparingInt(a -> a[0]));
for (int[] e : edges) {
int i = e[1], j = e[2];
p[find(i)] = find(j);
if (find(0) == find(m * n - 1)) {
return e[0];
}
}
return 0;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}Binary search + BFS:
class Solution {
public int minimumEffortPath(int[][] heights) {
int m = heights.length;
int n = heights[0].length;
int left = 0;
int right = 999999;
int[] dirs = {-1, 0, 1, 0, -1};
while (left < right) {
int mid = (left + right) >> 1;
boolean[][] vis = new boolean[m][n];
vis[0][0] = true;
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[]{0, 0});
while (!q.isEmpty()) {
int[] p = q.poll();
int i = p[0], j = p[1];
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && Math.abs(heights[i][j] - heights[x][y]) <= mid) {
q.offer(new int[]{x, y});
vis[x][y] = true;
}
}
}
if (vis[m - 1][n - 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}Union find:
class Solution {
public:
vector<int> p;
int minimumEffortPath(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
p.resize(m * n);
for (int i = 0; i < p.size(); ++i) p[i] = i;
vector<vector<int>> edges;
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
if (i < m - 1) edges.push_back({abs(heights[i][j] - heights[i + 1][j]), i * n + j, (i + 1) * n + j});
if (j < n - 1) edges.push_back({abs(heights[i][j] - heights[i][j + 1]), i * n + j, i * n + j + 1});
}
}
sort(edges.begin(), edges.end());
for (auto& e : edges)
{
int i = e[1], j = e[2];
p[find(i)] = find(j);
if (find(0) == find(m * n - 1)) return e[0];
}
return 0;
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
};Binary search + BFS:
class Solution {
public:
int minimumEffortPath(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
int left = 0, right = 999999;
vector<int> dirs = {-1, 0, 1, 0, -1};
while (left < right)
{
int mid = (left + right) >> 1;
vector<vector<bool>> vis(m, vector<bool>(n));
vis[0][0] = true;
queue<pair<int, int>> q;
q.push({0, 0});
while (!q.empty())
{
auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k)
{
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && abs(heights[i][j] - heights[x][y]) <= mid)
{
q.push({x, y});
vis[x][y] = true;
}
}
}
if (vis[m - 1][n - 1]) right = mid;
else left = mid + 1;
}
return left;
}
};Union find:
func minimumEffortPath(heights [][]int) int {
m, n := len(heights), len(heights[0])
p := make([]int, m*n)
for i := range p {
p[i] = i
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
edges := [][]int{}
for i, row := range heights {
for j, h := range row {
if i < m-1 {
s := []int{abs(h - heights[i+1][j]), i*n + j, (i+1)*n + j}
edges = append(edges, s)
}
if j < n-1 {
s := []int{abs(h - row[j+1]), i*n + j, i*n + j + 1}
edges = append(edges, s)
}
}
}
sort.Slice(edges, func(i, j int) bool {
return edges[i][0] < edges[j][0]
})
for _, e := range edges {
i, j := e[1], e[2]
p[find(i)] = find(j)
if find(0) == find(m*n-1) {
return e[0]
}
}
return 0
}
func abs(x int) int {
if x > 0 {
return x
}
return -x
}Binary search + BFS:
func minimumEffortPath(heights [][]int) int {
m, n := len(heights), len(heights[0])
left, right := 0, 999999
dirs := []int{-1, 0, 1, 0, -1}
for left < right {
mid := (left + right) >> 1
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
vis[0][0] = true
q := [][]int{{0, 0}}
for len(q) > 0 {
p := q[0]
q = q[1:]
i, j := p[0], p[1]
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && abs(heights[i][j]-heights[x][y]) <= mid {
q = append(q, []int{x, y})
vis[x][y] = true
}
}
}
if vis[m-1][n-1] {
right = mid
} else {
left = mid + 1
}
}
return left
}
func abs(x int) int {
if x > 0 {
return x
}
return -x
}