/**
* 1631. Path With Minimum Effort
* 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 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.
Note:
- rows == heights.length
- columns == heights[i].length
- 1 <= rows, columns <= 100
- 1 <= heights[i][j] <= 106
*/
See solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/PathWithMinEffortBinarySearch.java
A more traditional way to solve the problem is via A* which is implemented here:
Another way to solve the problem is via Union Find, which is implemented here:
The performance of the algorithms from fastest to slowest for this problem is : BinarySearch, UnionFind & lastly A*.
I will describe the binary search approach below as it’s a unique way to approach this problem. This problem serves as an excellent way to learn A* and Union Find approaches so recommend you look at the A* solution as well as the union find.
Per the problem spec it states that the maximum effort between two adjacent cells is between 1 and 10^6. So the solution can be considered as using binary search to traverse to the lowest possible effort. This can be done via splitting the effort band into two parts (low-mid, mid+1-high), if effort is found in the low to mid , you search further in that part. If it’s not found, you search in the upper part.
The algorithm translates as:
- Write a dfs routine to traverse the matrix from start cell to destination to validate if a path to reach destination exists with effort less than or equal to ‘delta’
- Write a binary search routine that calculates the lowest delta between 1 & 10^6 for which the above dfs has a valid solution.
- Calculate delta as mid (half way between low and high) and search for solution in dfs.
- If solution doesnt exist, search in mid+1 to high range.
- If solution exists further restrict search in low-mid range.
- Repeat 3 , 4, 5 until high > low
Here is the code:
public int minimumEffortPath(int[][] heights) {
rows = heights.length;
cols = heights[0].length;
target = (rows * cols) -1;
visited = new boolean[target+1];
this.heights = heights;
int low = 0;
int high = (int) Math.pow(10, 6);
while (low < high) {
Arrays.fill(visited, false);
int mid = (low + (high-low)/2);
boolean works = dfsTraverse(0, 0, mid);
if (works) {
high = mid;
} else {
low = mid+1;
}
}
return high;
}
public boolean dfsTraverse(int row, int col, int delta) {
int cellIndex = row * cols + col;
if (cellIndex == target) {
return true;
}
visited[row*cols+col] = true;
for (int i =0; i < rowMoves.length; i++) {
int newR = row + rowMoves[i];
int newC = col + colMoves[i];
if (newR < 0 || newR >= rows || newC < 0 || newC >= cols) {
continue;
}
int effort = Math.abs(heights[row][col] - heights[newR][newC]);
int newIndex = newR*cols+newC;
if (effort <= delta && !visited[newIndex]) {
boolean matches = dfsTraverse(newR, newC, delta);
if (matches) {
return true;
}
}
}
return false;
}