Time Complexity: $O(3^{N \times M})$
In the worst case, the recursion explores an exponential number of paths. For a grid of size $100 \times 100$, this is computationally infeasible.

Why it fails: The brute force method fails due to Time Limit Exceeded (TLE). The constraints allow for a grid size up to $100 \times 100$, resulting in 10,000 cells. Enumerating all paths in such a dense graph is impossible within standard time limits. We need an approach that polynomially finds the optimal path without traversing all possibilities.

Core Insight for Path With Minimum Effort

The key intuition for solving LeetCode 1631 efficiently lies in adapting the relaxation condition of Dijkstra's Algorithm.

In a standard Dijkstra implementation, we maintain the minimum cumulative distance to reach a node. Here, we maintain the minimum effort required to reach a node. The "effort" to reach a neighbor v from node u is not effort[u] + weight(u, v), but rather max(effort[u], weight(u, v)). This is because the path's cost is determined solely by the largest height difference encountered so far.

The algorithm maintains a strict invariant: at any point, the Priority Queue provides the reachable node with the lowest possible "maximum effort" discovered. By always expanding the path with the minimal "bottleneck" (the smallest maximum difference), we guarantee that when we reach the destination, we have found the path with the global minimum effort.

Visual Description: Imagine the grid as a network of nodes.

1. We start at (0,0) with a known effort of 0. All other nodes are initialized to infinity.
2. We place (0, 0) into a Min-Priority Queue.
3. The algorithm extracts the node with the smallest effort value.
4. From this node, we look at neighbors. If moving to a neighbor results in a path effort (max(current_effort, |height_diff|)) that is smaller than the neighbor's previously recorded effort, we update the neighbor's value and add it to the queue.
5. This process effectively "floods" the grid from the start, prioritizing paths that keep the height difference low, ensuring the first time we extract the bottom-right cell from the queue, we have the optimal answer.

Algorithm Strategy: Graph - Shortest Path (Dijkstra's Algorithm)

We implement Dijkstra's algorithm using a Min-Priority Queue and a 2D distance matrix (often named effort or dist).

1. State Representation: Let dist[r][c] store the minimum effort required to travel from (0, 0) to (r, c). Initialize all values to infinity (∞), except dist[0][0], which is 0.
2. Priority Queue: Use a Min-Heap to store tuples of (current_effort, row, col). This ensures we always process the cell reachable with the least effort first.
3. Initialization: Push (0, 0, 0) onto the Min-Heap.
4. Exploration Loop:
   • Pop the element with the smallest effort: (d, r, c).
   • If d > dist[r][c], this is an outdated entry; skip it.
   • If (r, c) is the bottom-right cell, return d.
   • Iterate through all 4 valid neighbors (nr, nc).
5. Relaxation Step:
   • Calculate the edge weight: weight = abs(heights[r][c] - heights[nr][nc]).
   • Calculate the new path effort: new_effort = max(d, weight).
   • If new_effort < dist[nr][nc]:
     • Update dist[nr][nc] = new_effort.
     • Push (new_effort, nr, nc) to the Min-Heap.

Execution Flow

Let's trace the logic for a small example. Input: heights = [[1, 2], [3, 8]]

1. Init:

   • dist matrix: [[0, ∞], [∞, ∞]]
   • PQ: [(0, 0, 0)] (effort, row, col)

2. Step 1:

   • Pop (0, 0, 0). Current cell is (0, 0) with height 1.
   • Neighbor (0, 1) (Height 2):
     • Edge weight: abs(1 - 2) = 1.
     • New effort: max(0, 1) = 1.
     • 1 < ∞, so update dist[0][1] = 1. Push (1, 0, 1).
   • Neighbor (1, 0) (Height 3):
     • Edge weight: abs(1 - 3) = 2.
     • New effort: max(0, 2) = 2.
     • 2 < ∞, so update dist[1][0] = 2. Push (2, 1, 0).
   • PQ state: [(1, 0, 1), (2, 1, 0)]

3. Step 2:

   • Pop (1, 0, 1). Current cell is (0, 1) with height 2.
   • Neighbor (1, 1) (Height 8):
     • Edge weight: abs(2 - 8) = 6.
     • New effort: max(1, 6) = 6.
     • 6 < ∞, so update dist[1][1] = 6. Push (6, 1, 1).
   • PQ state: [(2, 1, 0), (6, 1, 1)]

4. Step 3:

   • Pop (2, 1, 0). Current cell is (1, 0) with height 3.
   • Neighbor (1, 1) (Height 8):
     • Edge weight: abs(3 - 8) = 5.
     • New effort: max(2, 5) = 5.
     • 5 < 6 (current value in dist[1][1]), so update dist[1][1] = 5. Push (5, 1, 1).
   • PQ state: [(5, 1, 1), (6, 1, 1)] (Note: the old entry (6,1,1) remains but will be skipped later).

5. Step 4:

   • Pop (5, 1, 1). Current cell is target (1, 1).
   • Return 5.

Proof of Correctness

The algorithm is correct because it satisfies the greedy choice property and optimal substructure of Dijkstra's algorithm.

We are looking for a path that minimizes the function $f(p) = \max_{(u,v) \in p} |h_u - h_v|$. When we extract a node $u$ with effort $E_u$ from the priority queue, we claim that $E_u$ is the optimal (minimum) effort to reach $u$. Suppose there existed another path to $u$ with effort $E' < E_u$. This path must leave the set of visited nodes at some boundary node $v$ currently in the priority queue. However, the effort of any path through $v$ would be at least the effort to reach $v$. Since the priority queue yields the minimum value, the effort to reach $v$ must be $\ge E_u$. Since edge weights are non-negative, extending the path cannot decrease the maximum absolute difference. Thus, $E_u$ is indeed minimal.

Reference Implementation

C++ Solution for LeetCode 1631

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

using namespace std;

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int rows = heights.size();
        int cols = heights[0].size();
        
        // Min-priority queue to store {effort, row, col}
        // Ordered by effort ascending
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
        
        // Distance matrix to track min effort to reach each cell
        // Initialize with a large value
        vector<vector<int>> dist(rows, vector<int>(cols, 1e9));
        
        dist[0][0] = 0;
        pq.push({0, 0, 0});
        
        int dr[] = {0, 0, 1, -1};
        int dc[] = {1, -1, 0, 0};
        
        while (!pq.empty()) {
            auto current = pq.top();
            pq.pop();
            
            int currentEffort = current[0];
            int r = current[1];
            int c = current[2];
            
            // If we reached the bottom-right cell, return the effort
            if (r == rows - 1 && c == cols - 1) {
                return currentEffort;
            }
            
            // If we found a shorter path to this cell already, skip
            if (currentEffort > dist[r][c]) continue;
            
            // Check all 4 directions
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                    int weight = abs(heights[r][c] - heights[nr][nc]);
                    int newEffort = max(currentEffort, weight);
                    
                    // If this path offers a lower max-effort, update and push
                    if (newEffort < dist[nr][nc]) {
                        dist[nr][nc] = newEffort;
                        pq.push({newEffort, nr, nc});
                    }
                }
            }
        }
        return 0; // Should not reach here
    }
};

Java Solution for LeetCode 1631

java
import java.util.PriorityQueue;
import java.util.Arrays;

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length;
        int cols = heights[0].length;
        
        // Priority Queue stores arrays: {effort, row, col}
        // Orders by effort ascending
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        
        // dist[r][c] stores the minimum effort to reach (r, c)
        int[][] dist = new int[rows][cols];
        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        
        dist[0][0] = 0;
        pq.offer(new int[]{0, 0, 0});
        
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int currentEffort = current[0];
            int r = current[1];
            int c = current[2];
            
            if (r == rows - 1 && c == cols - 1) {
                return currentEffort;
            }
            
            // Optimization: Skip if we found a better path already
            if (currentEffort > dist[r][c]) continue;
            
            for (int[] dir : directions) {
                int nr = r + dir[0];
                int nc = c + dir[1];
                
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                    int weight = Math.abs(heights[r][c] - heights[nr][nc]);
                    // Key logic: effort is the max absolute difference along the path
                    int newEffort = Math.max(currentEffort, weight);
                    
                    if (newEffort < dist[nr][nc]) {
                        dist[nr][nc] = newEffort;
                        pq.offer(new int[]{newEffort, nr, nc});
                    }
                }
            }
        }
        
        return 0;
    }
}

Python Solution for LeetCode 1631

python
import heapq

class Solution:
    def minimumEffortPath(self, heights: list[list[int]]) -> int:
        rows, cols = len(heights), len(heights[0])
        
        # Priority Queue stores tuples: (effort, row, col)
        # Initialize with start node
        pq = [(0, 0, 0)]
        
        # dist matrix initialized to infinity
        dist = [[float('inf')] * cols for _ in range(rows)]
        dist[0][0] = 0
        
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        while pq:
            current_effort, r, c = heapq.heappop(pq)
            
            # If we reached the target, return result
            if r == rows - 1 and c == cols - 1:
                return current_effort
            
            # Skip if we found a better way to this cell
            if current_effort > dist[r][c]:
                continue
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                
                if 0 <= nr < rows and 0 <= nc < cols:
                    weight = abs(heights[r][c] - heights[nr][nc])
                    new_effort = max(current_effort, weight)
                    
                    if new_effort < dist[nr][nc]:
                        dist[nr][nc] = new_effort
                        heapq.heappush(pq, (new_effort, nr, nc))
                        
        return 0