Path With Minimum Effort

Intuition

Binary search on maximum effort. Or Dijkstra where edge weight = abs(height difference) and we minimize the maximum edge on the path.

Algorithm

1Dijkstra with effort[i][j] = min effort to reach (i,j). effort = max(current_effort, abs(height diff)).
2Min-heap by effort. Return effort[m-1][n-1].

Common Pitfalls

•Minimize the maximum difference, not sum of differences. Use modified Dijkstra with max as combination operator.

Path With Minimum Effort.java

Java

// Approach: Dijkstra with effort = max absolute difference along path. Use min-heap on (effort, row, col).
// Time: O(n*m * log(n*m)) Space: O(n*m)
import java.util.*;

class Solution {
    public int minCostPath(int[][] heights) {
        int rows = heights.length;
        int columns = heights[0].length;

        int[][] effort = new int[rows][columns];
        for (int[] e : effort)
            Arrays.fill(e, Integer.MAX_VALUE);

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        pq.offer(new int[] { 0, 0, 0 });
        effort[0][0] = 0;

        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int r = curr[0], c = curr[1], currEff = curr[2];

            if (r == rows - 1 && c == columns - 1)
                return currEff;

            for (int[] d : dirs) {
                int nr = r + d[0];
                int nc = c + d[1];

                if (nr >= 0 && nr < rows && nc >= 0 && nc < columns) {
                    int diff = Math.abs(heights[nr][nc] - heights[r][c]);
                    int newEff = Math.max(currEff, diff);

                    if (newEff < effort[nr][nc]) {
                        effort[nr][nc] = newEff;
                        pq.offer(new int[] { nr, nc, newEff });
                    }
                }
            }
        }

        return -1;
    }
}

Was this solution helpful?