Path With Minimum Effort

• Initialize a global variable minEffort to Integer.MAX_VALUE.
• Create a visited grid of the same dimensions as heights, initialized to false.
• Call a recursive function, let's say dfs(0, 0, 0, visited, heights) from the starting cell.
• The dfs(row, col, currentMaxEffort) function works as follows:
  • If the current path's effort currentMaxEffort is already greater than or equal to the global minEffort, we can prune this path and return (optional optimization).
  • If the destination (rows-1, cols-1) is reached, update minEffort = min(minEffort, currentMaxEffort) and return.
  • Mark the current cell (row, col) as visited: visited[row][col] = true.
  • Iterate through all four neighbors (up, down, left, right).
  • For each valid and unvisited neighbor:
    • Calculate the effort to move to it: effort = abs(heights[row][col] - heights[neighbor_row][neighbor_col]).
    • The new maximum effort for the path is max(currentMaxEffort, effort).
    • Make a recursive call for the neighbor with this new maximum effort.
  • After exploring all neighbors, backtrack by un-marking the current cell: visited[row][col] = false.

The core idea is to perform a classic backtracking search on the grid. We define a recursive function that explores paths starting from (0, 0). This function keeps track of the maximum effort encountered so far along the current path.

To prevent infinite loops (e.g., moving back and forth between two cells), we use a visited boolean matrix to mark cells that are part of the current path being explored. When the recursion backtracks, we un-mark the cell, allowing it to be part of other potential paths.

The base case for the recursion is when we reach the destination cell (rows-1, columns-1). At this point, we have found one complete path, and we compare its effort with a globally maintained minimum effort, updating it if the current path's effort is smaller.

While simple, this method is highly impractical as the number of paths in a grid grows exponentially with its size.

1class Solution {2    int minEffort = Integer.MAX_VALUE;3 4    public int minimumEffortPath(int[][] heights) {5        backtrack(0, 0, 0, heights, new boolean[heights.length][heights[0].length]);6        return minEffort;7    }8 9    private void backtrack(int r, int c, int currentMax, int[][] heights, boolean[][] visited) {10        if (r == heights.length - 1 && c == heights[0].length - 1) {11            minEffort = Math.min(minEffort, currentMax);12            return;13        }14 15        visited[r][c] = true;16        int[] dr = {-1, 1, 0, 0};17        int[] dc = {0, 0, -1, 1};18 19        for (int i = 0; i < 4; i++) {20            int nr = r + dr[i];21            int nc = c + dc[i];22 23            if (nr >= 0 && nr < heights.length && nc >= 0 && nc < heights[0].length && !visited[nr][nc]) {24                int effort = Math.abs(heights[r][c] - heights[nr][nc]);25                int newMax = Math.max(currentMax, effort);26                // A small pruning optimization: if current path effort is already worse, skip27                if (newMax < minEffort) { 28                    backtrack(nr, nc, newMax, heights, visited);29                }30            }31        }32        visited[r][c] = false;33    }34}

• Define a search range for the answer. The minimum possible effort is 0, and the maximum is 10^6 - 1. Let's use low = 0 and high = 1000000.
• Perform a binary search on this range.
• In each iteration of the binary search, pick a mid value.
• Check if a path exists from (0, 0) to (rows-1, columns-1) where the effort of every step is at most mid. This check can be done with a graph traversal algorithm like BFS or DFS.
  • Path Existence Check (using BFS):
    • Initialize a queue and a visited array.
    • Add the starting cell (0, 0) to the queue and mark it as visited.
    • While the queue is not empty, dequeue a cell (r, c).
    • If (r, c) is the destination, a path exists, so return true.
    • Explore its neighbors. For each neighbor (nr, nc), if it's within bounds, not visited, and abs(heights[r][c] - heights[nr][nc]) <= mid, mark it as visited and enqueue it.
    • If the queue becomes empty and the destination was not reached, no such path exists, so return false.
• If the path existence check returns true, it means mid is a possible effort. We try for a better (smaller) solution, so we set ans = mid and high = mid - 1.
• If the check returns false, mid is too small. We need to allow more effort, so we set low = mid + 1.
• The loop terminates when low > high, and the final ans is the minimum effort required.

We can binary search for the minimum required effort k in the range [0, 10^6]. For each candidate effort mid that we test, we need to answer the question: "Is it possible to travel from (0, 0) to (rows-1, columns-1) such that the absolute height difference between any two adjacent cells on the path is at most mid?"

This question can be answered efficiently using a graph traversal like Breadth-First Search (BFS) or Depth-First Search (DFS). We treat the grid as a graph where an edge between two cells exists only if the effort to cross it is less than or equal to mid. We then simply check for connectivity between the start and end cells.

• If a path exists for a given mid, it means mid is a valid effort. We then try to find an even smaller effort by searching in the lower half of the range: high = mid - 1.
• If no path exists, mid is too restrictive. We must allow for a larger effort, so we search in the upper half: low = mid + 1.

The smallest mid for which a path exists is our final answer.

1class Solution {2    public int minimumEffortPath(int[][] heights) {3        int left = 0, right = 1000000;4        int result = right;5        while (left <= right) {6            int mid = left + (right - left) / 2;7            if (canReachDestination(heights, mid)) {8                result = mid;9                right = mid - 1;10            } else {11                left = mid + 1;12            }13        }14        return result;15    }16 17    private boolean canReachDestination(int[][] heights, int maxEffort) {18        int rows = heights.length;19        int cols = heights[0].length;20        boolean[][] visited = new boolean[rows][cols];21        java.util.Queue<int[]> queue = new java.util.LinkedList<>();22 23        queue.offer(new int[]{0, 0});24        visited[0][0] = true;25 26        int[] dr = {-1, 1, 0, 0};27        int[] dc = {0, 0, -1, 1};28 29        while (!queue.isEmpty()) {30            int[] curr = queue.poll();31            int r = curr[0];32            int c = curr[1];33 34            if (r == rows - 1 && c == cols - 1) {35                return true;36            }37 38            for (int i = 0; i < 4; i++) {39                int nr = r + dr[i];40                int nc = c + dc[i];41 42                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]) {43                    if (Math.abs(heights[nr][nc] - heights[r][c]) <= maxEffort) {44                        visited[nr][nc] = true;45                        queue.offer(new int[]{nr, nc});46                    }47                }48            }49        }50        return false;51    }52}

• Get grid dimensions R and C.
• Create an efforts grid of size R x C to store the minimum effort to reach each cell, initialized to Integer.MAX_VALUE.
• Set the effort for the starting cell: efforts[0][0] = 0.
• Create a min-priority queue to store tuples of (effort, row, col). The priority queue will always return the tuple with the smallest effort.
• Add the starting cell information {0, 0, 0} to the priority queue.
• While the priority queue is not empty:
  • Extract the cell with the minimum effort from the queue: (d, r, c).
  • If d > efforts[r][c], this is a stale entry from a path that has already been improved. Skip it.
  • If (r, c) is the destination (R-1, C-1), we have found the path with the minimum possible effort. Return d.
  • For each of the four neighbors (nr, nc) of (r, c):
    • Calculate the effort to move from (r, c) to (nr, nc): edgeEffort = abs(heights[r][c] - heights[nr][nc]).
    • The effort of the path to the neighbor via (r, c) is max(d, edgeEffort).
    • If this new path effort is less than the currently known minimum effort to reach (nr, nc) (efforts[nr][nc]):
      • Update efforts[nr][nc] with this better value.
      • Add the new information {efforts[nr][nc], nr, nc} to the priority queue.

We treat the grid as a graph where each cell is a vertex. The weight of an edge between two adjacent cells is the absolute difference of their heights. The problem is to find a path from (0,0) to (rows-1, columns-1) that minimizes the maximum edge weight along the path.

Dijkstra's algorithm finds the shortest paths from a source to all other nodes. We can adapt it for our purpose. We'll maintain an efforts array, where efforts[r][c] stores the minimum effort (minimum of maximums) to reach cell (r,c). We use a priority queue to always explore the cell that is reachable with the minimum effort so far.

When we extract a cell (r, c) with effort d from the priority queue, d is guaranteed to be the minimum possible effort to reach that cell. We then relax its neighbors: for a neighbor (nr, nc), the effort to reach it via (r, c) is the maximum of d and the effort of the edge between (r, c) and (nr, nc). If this is better than the known effort for (nr, nc), we update it and add the neighbor to the queue. The first time we extract the destination cell, we have found our answer.

1class Solution {2    public int minimumEffortPath(int[][] heights) {3        int rows = heights.length;4        int cols = heights[0].length;5        int[][] efforts = new int[rows][cols];6        for (int[] row : efforts) {7            java.util.Arrays.fill(row, Integer.MAX_VALUE);8        }9        efforts[0][0] = 0;10 11        // Min-heap storing {effort, row, col}12        java.util.PriorityQueue<int[]> pq = new java.util.PriorityQueue<>((a, b) -> a[0] - b[0]);13        pq.offer(new int[]{0, 0, 0});14 15        int[] dr = {-1, 1, 0, 0};16        int[] dc = {0, 0, -1, 1};17 18        while (!pq.isEmpty()) {19            int[] curr = pq.poll();20            int d = curr[0];21            int r = curr[1];22            int c = curr[2];23 24            if (d > efforts[r][c]) {25                continue;26            }27 28            if (r == rows - 1 && c == cols - 1) {29                return d;30            }31 32            for (int i = 0; i < 4; i++) {33                int nr = r + dr[i];34                int nc = c + dc[i];35 36                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {37                    int newEffort = Math.max(d, Math.abs(heights[r][c] - heights[nr][nc]));38                    if (newEffort < efforts[nr][nc]) {39                        efforts[nr][nc] = newEffort;40                        pq.offer(new int[]{newEffort, nr, nc});41                    }42                }43            }44        }45        return 0; // Should not be reached46    }47}

• Get grid dimensions R and C. If R*C == 1, return 0.
• Create a list of all edges in the grid. An edge connects two adjacent cells. For each edge, store its effort (absolute height difference) and the indices of the two cells it connects. A cell (r, c) can be mapped to a single index r * C + c.
• Sort the list of edges in ascending order of their effort.
• Initialize a Union-Find (Disjoint Set Union) data structure with R * C elements, one for each cell.
• Iterate through the sorted edges (effort, u, v):
  • Perform a union operation on the two cells u and v.
  • After the union, check if the start cell (index 0) and the end cell (index R*C - 1) are in the same connected component using the find operation (find(0) == find(R*C - 1)).
  • If they are connected, it means we have just added the crucial edge that forms a path between start and end. Since we are processing edges in increasing order of effort, this edge's effort is the minimum possible maximum effort required. Return this effort.
• The loop will always find a path and return, so no return statement is needed after the loop.

This method is inspired by Kruskal's algorithm for finding a Minimum Spanning Tree (MST). The key insight is that we are looking for a path, and the cost of that path is its single most 'expensive' edge.

1. Edge List: First, we generate a list of all possible 'edges' in our grid. An edge connects two adjacent cells, and its 'weight' is the effort required to traverse it (the absolute difference in heights).

2. Sort Edges: We sort this list of edges by their weights in non-decreasing order.

3. Union-Find: We then iterate through the sorted edges. We use a Union-Find data structure to keep track of the connected components of cells. Initially, every cell is in its own component.

For each edge, we 'union' the components of the two cells it connects. After each union, we check if the start cell (0, 0) and the end cell (rows-1, columns-1) now belong to the same component. The first time they do, the weight of the edge we just added is the answer. Because we process edges from smallest to largest weight, this edge is the 'bottleneck' of the 'easiest' path, and thus its weight is the minimum possible effort.

1class Solution {2    class UnionFind {3        private int[] parent;4        private int[] rank;5 6        public UnionFind(int n) {7            parent = new int[n];8            rank = new int[n];9            for (int i = 0; i < n; i++) {10                parent[i] = i;11            }12        }13 14        public int find(int i) {15            if (parent[i] == i) return i;16            return parent[i] = find(parent[i]); // Path compression17        }18 19        public void union(int i, int j) {20            int rootI = find(i);21            int rootJ = find(j);22            if (rootI != rootJ) {23                // Union by rank24                if (rank[rootI] > rank[rootJ]) {25                    parent[rootJ] = rootI;26                } else if (rank[rootI] < rank[rootJ]) {27                    parent[rootI] = rootJ;28                } else {29                    parent[rootJ] = rootI;30                    rank[rootI]++;31                }32            }33        }34    }35 36    public int minimumEffortPath(int[][] heights) {37        int rows = heights.length;38        int cols = heights[0].length;39        if (rows == 1 && cols == 1) return 0;40 41        java.util.List<int[]> edges = new java.util.ArrayList<>();42        for (int r = 0; r < rows; r++) {43            for (int c = 0; c < cols; c++) {44                int currentCellId = r * cols + c;45                if (c + 1 < cols) {46                    int effort = Math.abs(heights[r][c] - heights[r][c + 1]);47                    edges.add(new int[]{effort, currentCellId, currentCellId + 1});48                }49                if (r + 1 < rows) {50                    int effort = Math.abs(heights[r][c] - heights[r + 1][c]);51                    edges.add(new int[]{effort, currentCellId, currentCellId + cols});52                }53            }54        }55 56        java.util.Collections.sort(edges, (a, b) -> a[0] - b[0]);57 58        UnionFind uf = new UnionFind(rows * cols);59        int startNode = 0;60        int endNode = rows * cols - 1;61 62        for (int[] edge : edges) {63            int effort = edge[0];64            int u = edge[1];65            int v = edge[2];66            uf.union(u, v);67            if (uf.find(startNode) == uf.find(endNode)) {68                return effort;69            }70        }71        return -1; // Should not be reached72    }73}