Path With Minimum Effort - Visualization

Graphs

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

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

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❯

  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

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...