G-37. Path With Minimum Effort

1. Problem Statement & Core Objective

You are a hiker preparing for an upcoming hike, represented by a 2D grid of size rows x columns called Heights. Each cell Heights[row][column] denotes the elevation at that specific coordinate.

• Start Position (Source): Top-left cell (0, 0)
• End Position (Destination): Bottom-right cell (rows - 1, cols - 1)
• Allowed Movement: Four cardinal directions (Up, Down, Left, Right).
• Route Effort Definition: The maximum absolute difference in heights between two consecutive cells along that entire route.

The primary objective is to find a route from the top-left to the bottom-right that minimizes this maximum effort.

2. Real-Life Analogy: Mountain Ridge Hiking

Imagine traversing a rugged mountain range represented by a grid of heights. To cross from the base camp (top-left) to the extraction point (bottom-right), you can take several paths.

• If you take a path with a giant cliff jump or a massive vertical wall, your single hardest climb (the maximum absolute height difference between consecutive steps) dictates how exhausting the entire trip is.
• Even if the rest of the trail is completely flat, one single extreme obstacle defines your total effort.
• Your goal as a smart hiker is to scan all possible paths, find the peak difficulty (maximum step difference) for each, and choose the trail where that peak difficulty is as low as possible.

3. Naive Exploration vs. Optimized Shortest Path Strategy

If we try to explore all possible paths using standard backtracking or Depth-First Search (DFS), the time complexity explodes exponentially $O(4^{N \times M})$ because you can revisit cells and cycle around.

Instead, we recognize this as an optimal path-finding problem with a bottleneck constraint (minimizing the maximum edge weight along a path).

• Whenever we hear "shortest path", "minimum effort", or "source-to-destination traversal with weighted transitions", Dijkstra's Algorithm naturally comes to mind.
• Why Dijkstra? While standard Dijkstra minimizes the sum of edge weights, we can adapt it to minimize the maximum edge weight encountered so far.

4. Core Mental Model: Modified Dijkstra's Algorithm

In our adapted Dijkstra approach:

1. Priority Queue (Min-Heap): Stores elements ordered by their current path effort. The top of the heap always yields the path with the minimum current effort.
2. Tuple Structure in PQ: (current_effort, row, column)
3. Distance/Effort Array: A 2D array initialized to Infinity to track the minimum possible effort required to reach each cell.
4. Path Effort Rule: When moving from cell $A$ to cell $B$, the effort for that step is $\vert Heights[A] - Heights[B]\vert$. The cumulative effort of the path up to cell $B$ is:

5. Step-by-Step Dry Run Example

Consider a small $2 \times 3$ or $3 \times 3$ grid. Let's trace how the priority queue processes cells, updates efforts, and avoids premature termination.

Grid Heights:
[ 1, 2, 2 ]
[ 3, 8, 2 ]
[ 5, 3, 5 ]

Initial Configuration:

• Source: (0, 0) with height 1.
• Distance Array: All set to Infinity, except Distance[0][0] = 0.
• Priority Queue (PQ): [(0, 0, 0)] representing (effort, row, col).

Iteration Walkthrough:

1. Pop (0, 0, 0) from PQ:

   • Standing at (0, 0) with accumulated effort 0.
   • Explore neighbors:
     • Right (0, 1) (height 2): Absolute diff = $\vert 1 - 2\vert = 1$. New cumulative effort = $\max(0, 1) = 1$. Since $1 < \infty$, update Distance[0][1] = 1 and push (1, 0, 1) to PQ.
     • Down (1, 0) (height 3): Absolute diff = $\vert 1 - 3\vert = 2$. New cumulative effort = $\max(0, 2) = 2$. Update Distance[1][0] = 2 and push (2, 1, 0) to PQ.

2. Pop (1, 0, 1) (Effort: 1, Coord: (0, 1)):

   • Explore neighbors:
     • Right (0, 2) (height 2): Diff = $\vert 2 - 2\vert = 0$. Effort = $\max(1, 0) = 1$. Push (1, 0, 2) to PQ.
     • Down (1, 1) (height 8): Diff = $\vert 2 - 8\vert = 6$. Effort = $\max(1, 6) = 6$. Push (6, 1, 1) to PQ.

3. Process Continues:

   • The algorithm evaluates alternative routes (e.g., going through lower height differences).
   • Once the destination (rows - 1, cols - 1) is popped from the priority queue, we are guaranteed to have found the minimum possible effort, and we can immediately return that effort value without examining further nodes.

6. Complete Algorithm Flow Walkthrough

7. Reference Implementation (C++ & Java)

C++ Implementation

#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int n = heights.size();
        int m = heights[0].size();
        
        // Min-heap priority queue storing: {effort, {row, col}}
        priority_queue<
            pair<int, pair<int, int>>, 
            vector<pair<int, pair<int, int>>>, 
            greater<pair<int, pair<int, int>>>
        > pq;
        
        // Distance matrix initialized to infinity
        vector<vector<int>> dist(n, vector<int>(m, 1e9));
        
        dist[0][0] = 0;
        pq.push({0, {0, 0}});
        
        int dr[] = {-1, 0, 1, 0};
        int dc[] = {0, 1, 0, -1};
        
        while(!pq.empty()) {
            auto it = pq.top();
            pq.pop();
            
            int effort = it.first;
            int row = it.second.first;
            int col = it.second.second;
            
            // If we reached the destination, return the effort
            if(row == n - 1 && col == m - 1) {
                return effort;
            }
            
            // Traverse all 4 directions
            for(int i = 0; i < 4; i++) {
                int newR = row + dr[i];
                int newC = col + dc[i];
                
                // Check if valid cell coordinates
                if(newR >= 0 && newR < n && newC >= 0 && newC < m) {
                    int newEffort = max(effort, abs(heights[row][col] - heights[newR][newC]));
                    
                    // If we found a strictly smaller effort path to the neighbor
                    if(newEffort < dist[newR][newC]) {
                        dist[newR][newC] = newEffort;
                        pq.push({newEffort, {newR, newC}});
                    }
                }
            }
        }
        
        return 0; // Fallback
    }
};

Java Implementation

import java.util.*;

class Solution {
    class Tuple {
        int distance;
        int row;
        int col;

        public Tuple(int distance, int row, int col) {
            this.distance = distance;
            this.row = row;
            this.col = col;
        }
    }

    public int minimumEffortPath(int[][] heights) {
        int n = heights.length;
        int m = heights[0].length;

        PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>(
            n * m, 
            Comparator.comparingInt(x -> x.distance)
        );

        int[][] dist = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], (int)(1e9));
        }

        dist[0][0] = 0;
        pq.add(new Tuple(0, 0, 0));

        int[] dr = {-1, 0, 1, 0};
        int[] dc = {0, 1, 0, -1};

        while(!pq.isEmpty()) {
            Tuple it = pq.poll();
            int effort = it.distance;
            int row = it.row;
            int col = it.col;

            if(row == n - 1 && col == m - 1) return effort;

            for(int i = 0; i < 4; i++) {
                int newR = row + dr[i];
                int newC = col + dc[i];

                if(newR >= 0 && newR < n && newC >= 0 && newC < m) {
                    int newEffort = Math.max(effort, Math.abs(heights[row][col] - heights[newR][newC]));
                    
                    if(newEffort < dist[newR][newC]) {
                        dist[newR][newC] = newEffort;
                        pq.add(new Tuple(newEffort, newR, newC));
                    }
                }
            }
        }
        
        return 0;
    }
}

8. Complexity Analysis

9. Summary and Key Takeaways

• Problem Nature: Finding a path that minimizes the maximum absolute edge weight along the route.
• Algorithm Mapping: Adapted Dijkstra's Algorithm perfectly fits bottleneck path problems.
• Priority Queue Ordering: Min-heap prioritizes routes with the smallest current maximum effort.
• Effort Calculation: Cumulative route effort is updated using $\max(\text{current\_effort}, \text{step\_diff})$.
• Early Exit Optimization: As soon as the destination node is popped from the priority queue, the optimal minimum effort is guaranteed and returned.
• Grid Traversal Technique: Use directional arrays (dr and dc) for clean, concise 4-directional neighbor exploration.