/**
* 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.
*/
See solution to the github code here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/PathWithMinimumEffortAStar.java
I also describe a solution to the same problem via binary search. Please have a look at that one for another approach to the same problem.
Below is another approach to solve this problem via union find.
Observation: We can utilize A* algorithm to traverse from source to destination cell while recording largest effort needed in traversing the path and thus calculating the maximum effort needed to traverse from source to destination cell.
On A* algorithm: The algorithm is structured to walk the path while leveraging a priority queue to retrieve the cell that can be visited with least effort (first in priority queue). And then adding new paths or paths that can be visited with less effort than what was previously recorded for them to the priority queue.
Here is the code:
public int minimumEffortPath(int[][] heights) {
int rows = heights.length;
int cols = heights[0].length;
int totalCells = (rows * cols);
Cell [] cells = new Cell[totalCells];
for (int i =0 ; i < totalCells; i++) {
cells[i] = new Cell(i);
}
PriorityQueue<Cell> priorityQueue = new PriorityQueue<>(
Comparator.comparingInt(l -> l.maxEffortToReachCell)
);
cells[0].maxEffortToReachCell = 0;
int [] rowMoves = {1, -1, 0, 0};
int [] colMoves = {0, 0, -1, 1};
priorityQueue.add(cells[0]);
while (!priorityQueue.isEmpty()) {
Cell theCell = priorityQueue.poll();
int row = theCell.cellId / cols;
int col = (theCell.cellId % cols);
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]);
effort = Math.max(theCell.maxEffortToReachCell, effort);
int newCellId = (newR*cols) + newC;
if (cells[newCellId].maxEffortToReachCell > effort) {
cells[newCellId].maxEffortToReachCell = effort;
priorityQueue.add(cells[newCellId]);
}
}
}
return cells[totalCells-1].maxEffortToReachCell;
}