Path with minimum Effort

Problem Link : (Path With Minimum Effort)

Problem Statement

You have a 2D array heights[][] of size rows × columns. Each cell contains an integer height. You start at the top‑left cell (0,0) and want to reach the bottom‑right cell (rows‑1, columns‑1). You can move up, down, left, or right. The effort of a path is defined as the maximum absolute difference in heights between any two consecutive cells along the path.

Return the minimum possible effort required to travel from start to end.

Intuition

This problem requires minimizing the path's maximum edge cost, where each edge cost is |height[u] − height[v]|. You want the path where that maximum is as small as possible.

This matches a Dijkstra-style shortest-path problem, but instead of summing edge weights, you use:

newEffort = max(currentEffort, abs(height[u]−height[v]))

and always expand the cell with the minimum currentEffort first. That ensures when the destination is dequeued, its effort is minimized.

Algorithm (Modified Dijkstra)

  1. Create a 2D array effort[r][c], initialized to a large value (e.g., 1e9).

  2. Set effort[0][0] = 0.

  3. Prepare a min-heap (priority queue) of (effort, row, col) tuples.

  4. Push (0, 0, 0) to the heap.

  5. While the heap is not empty:

    • Extract the smallest-effort tuple (currEff, r, c).

    • If (r, c) is the destination, return currEff.

    • For each of its four neighbors (nr, nc) within bounds:

      • Compute stepEff = abs(height[r][c] − height[nr][nc]).

      • Compute newEff = max(currEff, stepEff).

      • If newEff < effort[nr][nc]:

        • Update effort[nr][nc] = newEff.

        • Push (newEff, nr, nc) into the heap.

  6. If destination never extracted, return ‑1 (or 0 if guaranteed reachable).

Java Code Example

class Solution {
    static class Cell implements Comparable<Cell> {
        int effort, r, c;
        Cell(int e, int r, int c) { this.effort = e; this.r = r; this.c = c; }
        public int compareTo(Cell other) { return this.effort - other.effort; }
    }

    public int minimumEffortPath(int[][] heights) {
        int n = heights.length, m = heights[0].length;
        int[][] effort = new int[n][m];
        for (int[] row: effort) Arrays.fill(row, Integer.MAX_VALUE);
        effort[0][0] = 0;

        PriorityQueue<Cell> pq = new PriorityQueue<>();
        pq.offer(new Cell(0, 0, 0));
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

        while (!pq.isEmpty()) {
            Cell curr = pq.poll();
            if (curr.r == n-1 && curr.c == m-1) return curr.effort;
            if (curr.effort > effort[curr.r][curr.c]) continue;

            for (int[] d : dirs) {
                int nr = curr.r + d[0], nc = curr.c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                    int diff = Math.abs(heights[curr.r][curr.c] - heights[nr][nc]);
                    int newEff = Math.max(curr.effort, diff);
                    if (newEff < effort[nr][nc]) {
                        effort[nr][nc] = newEff;
                        pq.offer(new Cell(newEff, nr, nc));
                    }
                }
            }
        }
        return -1;
    }
}

Dry Run (Example)

heights = [
  [1, 2, 2],
  [3, 8, 2],
  [5, 3, 5]
]

Time and Space Complexity

Alternative: Binary Search + BFS

Another approach is binary-search over effort threshold E:

  1. Binary search E between 0 and max possible height difference.

  2. In canReach(E), perform BFS/DFS only traversing edges with |height diff| ≤ E.

  3. If BFS reaches destination, reduce search range; otherwise increase it.

  4. Final answer is smallest E passing canReach.

This achieves complexity O(log(maxHeight) · R · C) but is often slower in practice.

Final Notes