Path With Minimum Effort
Using Graph Traversal

Problem Statement

Imagine you're a hiker navigating a mountainous terrain. You're given a 2D grid heights of dimensions rows × columns, where each element represents the elevation at that cell.

Your goal is to move from the top-left corner (0, 0) to the bottom-right corner (rows-1, columns-1), moving only up, down, left, or right at each step.

The effort of a path is defined as the maximum absolute difference in heights between any two adjacent cells on that path. Your task is to find the path that minimizes this effort.

Algorithm Steps

1. Define directions for moving up, down, left, and right.
2. Use a priority queue to keep track of (effort, row, col).
3. Initialize a 2D array efforts with Infinity and set efforts[0][0] = 0.
4. While the priority queue is not empty:
1. Pop the cell with the least current effort.
2. If it's the bottom-right cell, return the current effort.
3. For each neighbor:
   • Calculate the height difference.
   • Compute the max between current path effort and the new diff.
   • If it's smaller than the stored effort, update and push into queue.
5. Return -1 if no path is found (theoretically unreachable).

Code

function minimumEffortPath(heights) {
  const rows = heights.length;
  const cols = heights[0].length;
  const directions = [[0,1],[1,0],[-1,0],[0,-1]];
  const efforts = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
  const heap = [[0, 0, 0]]; // [effort, x, y]
  efforts[0][0] = 0;

  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]);
    const [effort, x, y] = heap.shift();

    if (x === rows - 1 && y === cols - 1) return effort;

    for (const [dx, dy] of directions) {
      const nx = x + dx;
      const ny = y + dy;
      if (nx >= 0 && ny >= 0 && nx < rows && ny < cols) {
        const diff = Math.abs(heights[nx][ny] - heights[x][y]);
        const maxEffort = Math.max(effort, diff);
        if (maxEffort < efforts[nx][ny]) {
          efforts[nx][ny] = maxEffort;
          heap.push([maxEffort, nx, ny]);
        }
      }
    }
  }
  return -1;
}

const heights = [[1,2,2],[3,8,2],[5,3,5]];
console.log("Minimum Effort:", minimumEffortPath(heights));