In this guide, you will get 1631. Path With Minimum Effort LeetCode Solution with the best time and space complexity. The solution to Path With Minimum Effort problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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].
1631. Path With Minimum Effort LeetCode Solution in C++
struct T {
int i;
int j;
int d; // the maximum difference of (i, j) and its neighbors
};
class Solution {
public:
int minimumEffortPath(vector<vector<int>>& heights) {
constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int m = heights.size();
const int n = heights[0].size();
auto compare = [](const T& a, const T& b) { return a.d > b.d; };
priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);
// diff[i][j] := the maximum absolute difference to reach (i, j)
vector<vector<int>> diff(m, vector<int>(n, INT_MAX));
vector<vector<bool>> seen(m, vector<bool>(n));
minHeap.emplace(0, 0, 0);
diff[0][0] = 0;
while (!minHeap.empty()) {
const auto [i, j, d] = minHeap.top();
minHeap.pop();
if (i == m - 1 && j == n - 1)
return d;
seen[i][j] = true;
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seen[x][y])
continue;
const int newDiff = abs(heights[i][j] - heights[x][y]);
const int maxDiff = max(diff[i][j], newDiff);
if (diff[x][y] > maxDiff) {
diff[x][y] = maxDiff;
minHeap.emplace(x, y, maxDiff);
}
}
}
throw;
}
}; /* code provided by PROGIEZ */
1631. Path With Minimum Effort LeetCode Solution in Java
class Solution {
public int minimumEffortPath(int[][] heights) {
// d := the maximum difference of (i, j) and its neighbors
record T(int i, int j, int d) {}
final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
final int m = heights.length;
final int n = heights[0].length;
Queue<T> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.d, b.d));
// dist[i][j] := the maximum absolute difference to reach (i, j)
int[][] diff = new int[m][n];
Arrays.stream(diff).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
boolean[][] seen = new boolean[m][n];
minHeap.offer(new T(0, 0, 0));
diff[0][0] = 0;
while (!minHeap.isEmpty()) {
final int i = minHeap.peek().i;
final int j = minHeap.peek().j;
final int d = minHeap.poll().d;
if (i == m - 1 && j == n - 1)
return d;
seen[i][j] = true;
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seen[x][y])
continue;
final int newDiff = Math.abs(heights[i][j] - heights[x][y]);
final int maxDiff = Math.max(diff[i][j], newDiff);
if (diff[x][y] > maxDiff) {
diff[x][y] = maxDiff;
minHeap.offer(new T(x, y, maxDiff));
}
}
}
throw new IllegalArgumentException();
}
} // code provided by PROGIEZ
1631. Path With Minimum Effort LeetCode Solution in Python
class Solution:
def minimumEffortPath(self, heights: list[list[int]]) -> int:
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
m = len(heights)
n = len(heights[0])
# diff[i][j] := the maximum absolute difference to reach (i, j)
diff = [[math.inf] * n for _ in range(m)]
seen = set()
minHeap = [(0, 0, 0)] # (d, i, j)
diff[0][0] = 0
while minHeap:
d, i, j = heapq.heappop(minHeap)
if i == m - 1 and j == n - 1:
return d
seen.add((i, j))
for dx, dy in dirs:
x = i + dx
y = j + dy
if x < 0 or x == m or y < 0 or y == n:
continue
if (x, y) in seen:
continue
newDiff = abs(heights[i][j] - heights[x][y])
maxDiff = max(diff[i][j], newDiff)
if diff[x][y] > maxDiff:
diff[x][y] = maxDiff
heapq.heappush(minHeap, (diff[x][y], x, y)) # code by PROGIEZ
