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.

Examples❯

Heights Grid	Minimum Effort	Description
[[1,2,2],[3,8,2],[5,3,5]]	2	Optimal path keeps height differences ≤ 2
[[1,2,3],[3,8,4],[5,3,5]]	1	There exists a smoother path with only 1 max height difference
[[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]	0	All steps are between same or equal heights
[[1]]	0	Only one cell, no movement needed
[]	0	Empty grid has no path

Visualization Player

Solution❯

Understanding the Problem

We are given a 2D grid of heights. Each cell represents a height value. Our goal is to travel from the top-left cell (0,0) to the bottom-right cell (m-1,n-1).

But here's the twist: You can move only in the four directions — up, down, left, or right — and the effort of moving from one cell to another is defined as the absolute difference in their height values.

The total effort of a path is determined by the maximum effort taken in a single step along that path. So, we're not minimizing the total sum of efforts, but the maximum height difference in any step on the path.

In short: Find a path from (0,0) to (m-1,n-1) such that the largest step effort on that path is as small as possible.

Step-by-Step Solution with Example

Step 1: Represent the grid as a graph

Each cell is treated like a graph node. It is connected to its 4 neighbors (up, down, left, right) via edges. The weight of each edge is the absolute difference in heights between the two connected cells.

Step 2: Choose the right algorithm

Since we're trying to minimize the maximum edge weight on the path, we need a strategy that always picks the next move with the least maximum effort. This leads us to a modified Dijkstra’s algorithm.

Step 3: Use a priority queue (min-heap)

We'll use a min-heap to keep track of the cells we're about to explore. The heap will store entries like (effort, x, y), where effort is the current maximum step effort taken to reach cell (x,y).

Step 4: Initialize the data structures

Create a 2D array effortTo[x][y] to record the minimum effort to reach each cell, initialized with Infinity.
Push the start cell (0,0) into the priority queue with 0 effort.

Step 5: Traverse using the priority queue

At each step:

Pop the cell with the minimum effort from the queue.
Check if it's the destination. If so, return the effort.
For all valid neighboring cells:

Compute the effort to reach that neighbor as max(current effort, abs(height difference)).
If this is less than the previously stored effort to reach that cell, update it and push into the queue.

Step 6: Walkthrough with Example

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

Start at (0,0) → height = 1
Move to (0,1): effort = |1-2| = 1
Then (0,2): |2-2| = 0, max effort so far = 1
Then (1,2): |2-2| = 0, still 1
Then (2,2): |2-5| = 3, now max effort is 3 on this path
But there may be another path where this max value is lower — so we keep exploring
The best path ends up being (0,0) → (0,1) → (0,2) → (1,2) → (2,2) with max effort = 2

Edge Cases

Single cell grid: If the grid has only one cell, no movement is needed. Return 0.
All cells have the same height: Every step effort will be zero. So the total path effort is 0.
Non-square grid: Works the same. Shape of grid doesn’t affect the algorithm.
Multiple paths with same minimum effort: The algorithm returns the first one it finds.

Finally

This problem is a clever twist on Dijkstra’s shortest path algorithm — instead of summing edge weights, we focus on minimizing the maximum edge weight on a path. It's a great example of customizing graph algorithms for problem-specific constraints.

Always start by understanding the core objective — here, minimizing the maximum effort — and then pick the right strategy (greedy, BFS, Dijkstra, etc.) based on that goal.

Algorithm Steps❯

Define directions for moving up, down, left, and right.
Use a priority queue to keep track of (effort, row, col).
Initialize a 2D array efforts with Infinity and set efforts[0][0] = 0.
While the priority queue is not empty:

Pop the cell with the least current effort.
If it's the bottom-right cell, return the current effort.
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.

Return -1 if no path is found (theoretically unreachable).

Code

JavaScript

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));

⬅ Previous TopicShortest Distance in a Binary Maze using BFS

Next Topic ⮕Cheapest Flights Within K Stops - Graph Problem

Comments

Loading comments...