Path With Minimum Effort
Medium · Advanced Graphs · Explanation and code example
Shortest Path Faster Algorithm
How it works
SPFA can also solve this problem by treating effort as the distance metric. We use a queue to process cells and update their minimum effort when a better path is found. Unlike Dijkstra's, SPFA does not require a priority queue, trading off guaranteed optimal ordering for simplicity and potential efficiency on some inputs.
Steps
- Initialize a
distarray with infinity for all cells exceptdist[0] = 0for the starting cell. - Use a queue and add the starting cell. Track which cells are currently in the queue.
- Dequeue a cell and mark it as not in the queue.
- For each neighbor, compute the new effort as
max(current effort, height difference). - If the new effort is less than the neighbor's recorded effort, update it. If the neighbor is not in the queue, add it.
- Continue until the queue is empty and return
distfor the bottom-right cell.
Complexity
- Time complexity:
O(m * n)time in average case.O(m ^ 2 * n ^ 2)time in worst case.
- Space complexity:
O(m * n)
Where
mis the number of rows andnis the number of columns in the given matrix.
Things to watch for
Summing Differences Instead of Taking Maximum
The effort of a path is defined as the maximum absolute difference along the path, not the sum. Using addition instead of max() when computing the new effort will give incorrect results. Always compute newEffort = max(currentEffort, abs(height[current] - height[neighbor])).
Confusing Single-Cell Grids
When the grid has only one cell, the answer is 0 since we are already at the destination. Some implementations may fail to handle this edge case, especially when the algorithm expects at least one move. Check for ROWS == 1 && COLS == 1 as a base case or ensure your algorithm naturally returns 0.
Incorrect Distance Initialization
In Dijkstra's algorithm, all distances should be initialized to infinity except for the starting cell which should be 0. Some implementations mistakenly initialize all distances to zero or forget to set the starting distance, causing the algorithm to skip valid relaxations or produce incorrect minimum efforts.
Python code example
from typing import List
from collections import deque
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
ROWS, COLS = len(heights), len(heights[0])
dist = [float('inf')] * (ROWS * COLS)
dist[0] = 0
in_queue = [False] * (ROWS * COLS)
def index(r, c):
return r * COLS + c
queue = deque([0])
in_queue[0] = True
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while queue:
u = queue.popleft()
in_queue[u] = False
r, c = divmod(u, COLS)
for dr, dc in directions:
newR, newC = r + dr, c + dc
if 0 <= newR < ROWS and 0 <= newC < COLS:
v = index(newR, newC)
weight = abs(heights[r][c] - heights[newR][newC])
new_dist = max(dist[u], weight)
if new_dist < dist[v]:
dist[v] = new_dist
if not in_queue[v]:
queue.append(v)
in_queue[v] = True
return dist[ROWS * COLS - 1]
C++ code example
class Solution {
public:
int minimumEffortPath(vector<vector<int>>& heights) {
int ROWS = heights.size(), COLS = heights[0].size();
vector<int> dist(ROWS * COLS, INT_MAX);
dist[0] = 0;
vector<bool> inQueue(ROWS * COLS, false);
queue<int> q;
q.push(0);
inQueue[0] = true;
vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while (!q.empty()) {
int u = q.front();
q.pop();
inQueue[u] = false;
int r = u / COLS, c = u % COLS;
for (const auto& dir : directions) {
int newR = r + dir[0], newC = c + dir[1];
if (newR >= 0 && newC >= 0 && newR < ROWS && newC < COLS) {
int v = newR * COLS + newC;
int weight = abs(heights[r][c] - heights[newR][newC]);
int newDist = max(dist[u], weight);
if (newDist < dist[v]) {
dist[v] = newDist;
if (!inQueue[v]) {
q.push(v);
inQueue[v] = true;
}
}
}
}
}
return dist[ROWS * COLS - 1];
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.