ProgramGuru

Path With Minimum Effort in Grid using Graphs

Problem and examples

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.

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

Explore Path With Minimum Effort

Load an example or enter your own input. Use the player controls to follow each change.

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.

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

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))

typedef struct {
    int x, y, effort;
} Cell;

void push(Cell heap[], int *size, Cell val) {
    heap[(*size)++] = val;
    int i = *size - 1;
    while (i > 0 && heap[i].effort < heap[(i - 1) / 2].effort) {
        Cell temp = heap[i]; heap[i] = heap[(i - 1) / 2]; heap[(i - 1) / 2] = temp;
        i = (i - 1) / 2;
    }
}

Cell pop(Cell heap[], int *size) {
    Cell top = heap[0];
    heap[0] = heap[--(*size)];
    int i = 0;
    while (2 * i + 1 < *size) {
        int smallest = 2 * i + 1;
        if (2 * i + 2 < *size && heap[2 * i + 2].effort < heap[2 * i + 1].effort)
            smallest = 2 * i + 2;
        if (heap[i].effort <= heap[smallest].effort) break;
        Cell temp = heap[i]; heap[i] = heap[smallest]; heap[smallest] = temp;
        i = smallest;
    }
    return top;
}

int minimumEffortPath(int** heights, int rows, int cols) {
    int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    int** effort = malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; i++) {
        effort[i] = malloc(cols * sizeof(int));
        for (int j = 0; j < cols; j++) effort[i][j] = INT_MAX;
    }

    Cell heap[rows * cols * 4];
    int heapSize = 0;
    effort[0][0] = 0;
    push(heap, &heapSize, (Cell){0, 0, 0});

    while (heapSize > 0) {
        Cell curr = pop(heap, &heapSize);
        if (curr.x == rows - 1 && curr.y == cols - 1) return curr.effort;
        for (int d = 0; d < 4; d++) {
            int nx = curr.x + dirs[d][0], ny = curr.y + dirs[d][1];
            if (nx >= 0 && ny >= 0 && nx < rows && ny < cols) {
                int diff = abs(heights[nx][ny] - heights[curr.x][curr.y]);
                int maxEff = MAX(curr.effort, diff);
                if (maxEff < effort[nx][ny]) {
                    effort[nx][ny] = maxEff;
                    push(heap, &heapSize, (Cell){nx, ny, maxEff});
                }
            }
        }
    }
    return -1;
}

int main() {
    int data[3][3] = {{1,2,2},{3,8,2},{5,3,5}};
    int* heights[3] = {data[0], data[1], data[2]};
    printf("Minimum Effort: %d\n", minimumEffortPath(heights, 3, 3));
    return 0;
}

C++ implementation

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Cell {
    int x, y, effort;
    bool operator>(const Cell& other) const {
        return effort > other.effort;
    }
};

int minimumEffortPath(vector<vector<int>>& heights) {
    int rows = heights.size();
    int cols = heights[0].size();
    vector<vector<int>> effort(rows, vector<int>(cols, INT_MAX));
    priority_queue<Cell, vector<Cell>, greater<>> pq;
    pq.push({0, 0, 0});
    effort[0][0] = 0;

    vector<pair<int, int>> directions = {{0,1},{1,0},{-1,0},{0,-1}};

    while (!pq.empty()) {
        Cell curr = pq.top(); pq.pop();
        if (curr.x == rows - 1 && curr.y == cols - 1) return curr.effort;
        for (auto [dx, dy] : directions) {
            int nx = curr.x + dx, ny = curr.y + dy;
            if (nx >= 0 && ny >= 0 && nx < rows && ny < cols) {
                int diff = abs(heights[nx][ny] - heights[curr.x][curr.y]);
                int maxEffort = max(curr.effort, diff);
                if (maxEffort < effort[nx][ny]) {
                    effort[nx][ny] = maxEffort;
                    pq.push({nx, ny, maxEffort});
                }
            }
        }
    }
    return -1;
}

int main() {
    vector<vector<int>> heights = {{1,2,2},{3,8,2},{5,3,5}};
    cout << "Minimum Effort: " << minimumEffortPath(heights) << endl;
    return 0;
}

Python implementation

import heapq

def minimum_effort_path(heights):
    rows, cols = len(heights), len(heights[0])
    effort = [[float('inf')] * cols for _ in range(rows)]
    effort[0][0] = 0
    min_heap = [(0, 0, 0)]  # effort, x, y

    directions = [(0,1), (1,0), (-1,0), (0,-1)]

    while min_heap:
        curr_effort, x, y = heapq.heappop(min_heap)
        if x == rows - 1 and y == cols - 1:
            return curr_effort
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols:
                diff = abs(heights[nx][ny] - heights[x][y])
                max_effort = max(curr_effort, diff)
                if max_effort < effort[nx][ny]:
                    effort[nx][ny] = max_effort
                    heapq.heappush(min_heap, (max_effort, nx, ny))
    return -1

heights = [[1,2,2],[3,8,2],[5,3,5]]
print("Minimum Effort:", minimum_effort_path(heights))

Java implementation

import java.util.*;

public class MinimumEffortPath {
    static class Cell implements Comparable<Cell> {
        int x, y, effort;
        Cell(int x, int y, int e) { this.x = x; this.y = y; this.effort = e; }
        public int compareTo(Cell o) { return this.effort - o.effort; }
    }

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

        PriorityQueue<Cell> pq = new PriorityQueue<>();
        pq.offer(new Cell(0, 0, 0));
        effort[0][0] = 0;

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

        while (!pq.isEmpty()) {
            Cell curr = pq.poll();
            if (curr.x == rows - 1 && curr.y == cols - 1) return curr.effort;
            for (int[] d : dirs) {
                int nx = curr.x + d[0], ny = curr.y + d[1];
                if (nx >= 0 && ny >= 0 && nx < rows && ny < cols) {
                    int diff = Math.abs(heights[nx][ny] - heights[curr.x][curr.y]);
                    int maxEff = Math.max(curr.effort, diff);
                    if (maxEff < effort[nx][ny]) {
                        effort[nx][ny] = maxEff;
                        pq.offer(new Cell(nx, ny, maxEff));
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[][] heights = {{1,2,2},{3,8,2},{5,3,5}};
        System.out.println("Minimum Effort: " + minimumEffortPath(heights));
    }
}

JavaScript implementation

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

Go implementation

package main

import (
  "container/heap"
  "fmt"
  "math"
)

type Cell struct {
  x, y, effort int
}

type MinHeap []Cell

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].effort < h[j].effort }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Cell)) }
func (h *MinHeap) Pop() interface{} {
  old := *h
  n := len(old)
  x := old[n-1]
  *h = old[0 : n-1]
  return x
}

func minimumEffortPath(heights [][]int) int {
  rows := len(heights)
  cols := len(heights[0])
  effort := make([][]int, rows)
  for i := range effort {
    effort[i] = make([]int, cols)
    for j := range effort[i] {
      effort[i][j] = math.MaxInt32
    }
  }
  dirs := [][]int{{0,1},{1,0},{-1,0},{0,-1}}
  h := &MinHeap{{0,0,0}}
  heap.Init(h)
  effort[0][0] = 0
  for h.Len() > 0 {
    curr := heap.Pop(h).(Cell)
    if curr.x == rows-1 && curr.y == cols-1 {
      return curr.effort
    }
    for _, d := range dirs {
      nx, ny := curr.x + d[0], curr.y + d[1]
      if nx >= 0 && ny >= 0 && nx < rows && ny < cols {
        diff := int(math.Abs(float64(heights[nx][ny] - heights[curr.x][curr.y])))
        maxEff := max(curr.effort, diff)
        if maxEff < effort[nx][ny] {
          effort[nx][ny] = maxEff
          heap.Push(h, Cell{nx, ny, maxEff})
        }
      }
    }
  }
  return -1
}

func max(a, b int) int {
  if a > b { return a }
  return b
}

func main() {
  heights := [][]int{{1,2,2},{3,8,2},{5,3,5}}
  fmt.Println("Minimum Effort:", minimumEffortPath(heights))
}

Rust implementation

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn minimum_effort_path(heights: Vec<Vec<i32>>) -> i32 {
    let rows = heights.len();
    let cols = heights[0].len();
    let directions = [(0,1), (1,0), (0,-1), (-1,0)];
    let mut effort = vec![vec![i32::MAX; cols]; rows];
    let mut heap = BinaryHeap::new();

    effort[0][0] = 0;
    heap.push(Reverse((0, 0, 0))); // (effort, x, y)

    while let Some(Reverse((e, x, y))) = heap.pop() {
        if x == rows - 1 && y == cols - 1 {
            return e;
        }

        for (dx, dy) in directions.iter() {
            let nx = x as isize + dx;
            let ny = y as isize + dy;
            if nx >= 0 && ny >= 0 && (nx as usize) < rows && (ny as usize) < cols {
                let nx = nx as usize;
                let ny = ny as usize;
                let diff = (heights[nx][ny] - heights[x][y]).abs();
                let max_eff = e.max(diff);
                if max_eff < effort[nx][ny] {
                    effort[nx][ny] = max_eff;
                    heap.push(Reverse((max_eff, nx, ny)));
                }
            }
        }
    }
    -1
}

fn main() {
    let heights = vec![vec![1,2,2], vec![3,8,2], vec![5,3,5]];
    println!("Minimum Effort: {}", minimum_effort_path(heights));
}

Kotlin implementation

import java.util.PriorityQueue

data class Cell(val x: Int, val y: Int, val effort: Int): Comparable<Cell> {
    override fun compareTo(other: Cell): Int = this.effort - other.effort
}

fun minimumEffortPath(heights: Array<IntArray>): Int {
    val rows = heights.size
    val cols = heights[0].size
    val directions = arrayOf(intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1), intArrayOf(-1,0))
    val effort = Array(rows) { IntArray(cols) { Int.MAX_VALUE } }
    val pq = PriorityQueue<Cell>()

    effort[0][0] = 0
    pq.add(Cell(0, 0, 0))

    while (pq.isNotEmpty()) {
        val (x, y, e) = pq.poll()
        if (x == rows - 1 && y == cols - 1) return e

        for (d in directions) {
            val nx = x + d[0]
            val ny = y + d[1]
            if (nx in 0 until rows && ny in 0 until cols) {
                val diff = kotlin.math.abs(heights[nx][ny] - heights[x][y])
                val maxEff = maxOf(e, diff)
                if (maxEff < effort[nx][ny]) {
                    effort[nx][ny] = maxEff
                    pq.add(Cell(nx, ny, maxEff))
                }
            }
        }
    }
    return -1
}

fun main() {
    val heights = arrayOf(
        intArrayOf(1, 2, 2),
        intArrayOf(3, 8, 2),
        intArrayOf(5, 3, 5)
    )
    println("Minimum Effort: ${minimumEffortPath(heights)}")
}

Swift implementation

import Foundation

struct Cell: Comparable {
    let x: Int, y: Int, effort: Int
    static func < (a: Cell, b: Cell) -> Bool {
        return a.effort < b.effort
    }
}

func minimumEffortPath(_ heights: [[Int]]) -> Int {
    let rows = heights.count, cols = heights[0].count
    var efforts = Array(repeating: Array(repeating: Int.max, count: cols), count: rows)
    var heap = [Cell(x: 0, y: 0, effort: 0)]
    efforts[0][0] = 0
    let directions = [(0,1), (1,0), (-1,0), (0,-1)]

    while !heap.isEmpty {
        heap.sort(by: <)
        let current = heap.removeFirst()
        if current.x == rows - 1 && current.y == cols - 1 {
            return current.effort
        }
        for (dx, dy) in directions {
            let nx = current.x + dx, ny = current.y + dy
            if nx >= 0 && ny >= 0 && nx < rows && ny < cols {
                let diff = abs(heights[nx][ny] - heights[current.x][current.y])
                let maxEff = max(current.effort, diff)
                if maxEff < efforts[nx][ny] {
                    efforts[nx][ny] = maxEff
                    heap.append(Cell(x: nx, y: ny, effort: maxEff))
                }
            }
        }
    }
    return -1
}

let heights = [[1,2,2],[3,8,2],[5,3,5]]
print("Minimum Effort: \(minimumEffortPath(heights))")

TypeScript implementation

function minimumEffortPath(heights: number[][]): number {
  const rows = heights.length;
  const cols = heights[0].length;
  const directions = [[0,1],[1,0],[-1,0],[0,-1]];
  const efforts: number[][] = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
  const heap: [number, number, number][] = [[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: number[][] = [[1,2,2],[3,8,2],[5,3,5]];
console.log("Minimum Effort:", minimumEffortPath(heights));