Path With Minimum Effort

Problem Overview

Binary search on maximum effort.

See our study guide for structured GFG and LeetCode practice.

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?