Path with Minimum Effort

114.9k
0

Given an N×M matrix of heights, find a path from the top-left cell to the bottom-right cell with minimum effort.

Movement is allowed in four directions. Path effort equals the maximum absolute height difference between consecutive cells along the route. Return the minimum possible path effort.

Example 1

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]

Output: 2

Explanation: Route 1->3->5->3->5 has adjacent differences [2,2,2,2], so effort is 2.

Example 2

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]

Output: 1

Explanation: Route 1->2->3->4->5 has maximum adjacent difference 1.

Brute Force Approach

An effort limit converts the weighted grid into a reachability problem. Movement between adjacent cells is allowed only when the absolute height difference does not exceed the selected limit.

Testing limits from 0 upward guarantees that the first feasible value is optimal. Repeated BFS traversals, however, make the approach expensive when the height range is large.

Algorithm

  • Find the minimum and maximum grid heights and define H as their difference, providing a guaranteed upper bound for the required effort.

  • Test every effort limit from 0 to H in increasing order, ensuring that the first feasible limit is the minimum possible effort.

  • For each limit, initialize a fresh visited matrix and add the source cell to a BFS queue.

  • Process the queue and examine all four neighbors of every removed cell.

  • Add an unvisited neighbor when the absolute height difference does not exceed the current limit, preserving only allowed movements.

  • Return the current limit upon reaching the destination; the range ending at H guarantees a feasible value for a non-empty grid.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Check destination reachability under an effort limit.
bool canReach(vector<vector<int>>& heights, int limit) {
int rows = heights.size();
int cols = heights[0].size();
vector<vector<int>> visited(rows, vector<int>(cols, 0));
queue<pair<int, int>> q;
q.push({0, 0});
visited[0][0] = 1;
int dRow[4] = {-1, 0, 1, 0};
int dCol[4] = {0, 1, 0, -1};
// Explore every cell reachable within the limit.
while (!q.empty()) {
auto [row, col] = q.front();
q.pop();
if (row == rows - 1 && col == cols - 1) {
return true;
}
// Check all four neighboring cells.
for (int direction = 0; direction < 4; direction++) {
int nextRow = row + dRow[direction];
int nextCol = col + dCol[direction];
if (nextRow < 0 || nextRow >= rows ||
nextCol < 0 || nextCol >= cols ||
visited[nextRow][nextCol]) {
continue;
}
int difference = abs(
heights[row][col] - heights[nextRow][nextCol]
);
if (difference <= limit) {
visited[nextRow][nextCol] = 1;
q.push({nextRow, nextCol});
}
}
}
return false;
}
public:
// Return minimum possible maximum adjacent height difference.
int minimumEffortPath(vector<vector<int>>& heights) {
int minimumHeight = heights[0][0];
int maximumHeight = heights[0][0];
// Find a guaranteed upper bound for effort.
for (const vector<int>& row : heights) {
for (int height : row) {
minimumHeight = min(minimumHeight, height);
maximumHeight = max(maximumHeight, height);
}
}
// Test effort limits from smallest to largest.
for (int limit = 0; limit <= maximumHeight - minimumHeight; limit++) {
if (canReach(heights, limit)) {
return limit;
}
}
return 0;
}
};
// Driver code.
int main() {
vector<vector<int>> heights = {
{1, 2, 2}, {3, 8, 2}, {5, 3, 5}
};
Solution sol;
cout << sol.minimumEffortPath(heights);
return 0;
}

Complexity Analysis

Time Complexity: O(H×N×M), where N and M are the grid dimensions and H is the height range; up to H+1 limits run a complete BFS.

Space Complexity: O(N×M), where the visited matrix and BFS queue can each store up to N×M cells.

Better Approach

Threshold feasibility is monotonic: once a destination becomes reachable under an effort limit, every larger limit also remains feasible. Binary search uses such monotonicity to avoid testing every value.

Each middle value runs a BFS reachability check. A feasible threshold reduces the upper bound, while an infeasible threshold increases the lower bound.

Algorithm

  • Find the minimum and maximum grid heights and define the search range from 0 to their difference H.

  • Continue binary search while the lower bound is smaller than the upper bound and calculate the middle effort limit.

  • Run BFS with a fresh visited matrix, allowing movement only when the adjacent height difference does not exceed the middle value.

  • Set the upper bound to the middle value when BFS reaches the destination, preserving the possibility of a smaller feasible effort.

  • Set the lower bound to middle+1 when BFS fails, eliminating all infeasible limits up to the middle value.

  • Return the converged lower bound, representing the smallest effort that permits destination reachability.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Check destination reachability under an effort limit.
bool canReach(vector<vector<int>>& heights, int limit) {
int rows = heights.size();
int cols = heights[0].size();
vector<vector<int>> visited(rows, vector<int>(cols, 0));
queue<pair<int, int>> q;
q.push({0, 0});
visited[0][0] = 1;
int dRow[4] = {-1, 0, 1, 0};
int dCol[4] = {0, 1, 0, -1};
// Explore every cell reachable within the limit.
while (!q.empty()) {
auto [row, col] = q.front();
q.pop();
if (row == rows - 1 && col == cols - 1) {
return true;
}
// Check all four neighboring cells.
for (int direction = 0; direction < 4; direction++) {
int nextRow = row + dRow[direction];
int nextCol = col + dCol[direction];
if (nextRow < 0 || nextRow >= rows ||
nextCol < 0 || nextCol >= cols ||
visited[nextRow][nextCol]) {
continue;
}
int difference = abs(
heights[row][col] - heights[nextRow][nextCol]
);
if (difference <= limit) {
visited[nextRow][nextCol] = 1;
q.push({nextRow, nextCol});
}
}
}
return false;
}
public:
// Return minimum possible maximum adjacent height difference.
int minimumEffortPath(vector<vector<int>>& heights) {
int minimumHeight = heights[0][0];
int maximumHeight = heights[0][0];
// Find a guaranteed upper bound for effort.
for (const vector<int>& row : heights) {
for (int height : row) {
minimumHeight = min(minimumHeight, height);
maximumHeight = max(maximumHeight, height);
}
}
int low = 0;
int high = maximumHeight - minimumHeight;
// Binary search the smallest feasible effort limit.
while (low < high) {
int middle = low + (high - low) / 2;
if (canReach(heights, middle)) {
high = middle;
} else {
low = middle + 1;
}
}
return low;
}
};
// Driver code.
int main() {
vector<vector<int>> heights = {
{1, 2, 2}, {3, 8, 2}, {5, 3, 5}
};
Solution sol;
cout << sol.minimumEffortPath(heights);
return 0;
}

Complexity Analysis

Time Complexity: O(N×M×log H), where N and M are the grid dimensions and H is the height range; every binary-search iteration runs one BFS.

Space Complexity: O(N×M), where the visited matrix and BFS queue can each store up to N×M cells.

Optimal Approach

Every cell represents a graph vertex, while the absolute height difference between adjacent cells represents an edge weight. Path effort equals the largest edge weight on the path rather than the sum of all weights.

Dijkstra’s Algorithm adapts through minimax relaxation. A min-heap processes the route having the smallest known bottleneck, making the destination effort final when the destination is removed with a current heap value.

Algorithm

  • Initialize every cell effort as infinity, set the source effort to 0, and insert the source state into a min-heap.

  • Continue processing while the heap contains states and remove the cell having the smallest known route effort.

  • Skip the removed state when the heap effort differs from the stored effort, as the state represents an outdated route.

  • Return the current effort when the destination is removed, since the smallest available bottleneck cannot be improved later.

  • Examine all four valid neighbors and calculate the edge effort as the absolute height difference between both cells.

  • Calculate the candidate effort as the maximum of the current route effort and edge effort; upon improvement, update the neighbor and insert a fresh heap state.

  • Return 0 only as a defensive fallback after heap exhaustion. The fallback is never reached for a valid non-empty rectangular grid, because every cell is reachable through orthogonal moves.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Return minimum possible maximum adjacent height difference.
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));
using State = tuple<int, int, int>;
priority_queue<State, vector<State>, greater<State>> minHeap;
effort[0][0] = 0;
minHeap.push({0, 0, 0});
int dRow[4] = {-1, 0, 1, 0};
int dCol[4] = {0, 1, 0, -1};
// Process cells by smallest known route effort.
while (!minHeap.empty()) {
auto [currentEffort, row, col] = minHeap.top();
minHeap.pop();
// Skip an outdated heap state.
if (currentEffort != effort[row][col]) {
continue;
}
// Destination effort is final after extraction.
if (row == rows - 1 && col == cols - 1) {
return currentEffort;
}
// Relax all four neighboring cells.
for (int direction = 0; direction < 4; direction++) {
int nextRow = row + dRow[direction];
int nextCol = col + dCol[direction];
if (nextRow < 0 || nextRow >= rows ||
nextCol < 0 || nextCol >= cols) {
continue;
}
int edgeEffort = abs(
heights[row][col] - heights[nextRow][nextCol]
);
int candidate = max(currentEffort, edgeEffort);
if (candidate < effort[nextRow][nextCol]) {
effort[nextRow][nextCol] = candidate;
minHeap.push({candidate, nextRow, nextCol});
}
}
}
return 0;
}
};
// Driver code.
int main() {
vector<vector<int>> heights = {
{1, 2, 2}, {3, 8, 2}, {5, 3, 5}
};
Solution sol;
cout << sol.minimumEffortPath(heights);
return 0;
}

Complexity Analysis

Time Complexity: O(N×M×log(N×M)), where N and M are the grid dimensions; heap operations process O(N×M) cells and grid edges.

Space Complexity: O(N×M), where the effort matrix and min-heap can each store a number of states proportional to N×M.

Interview follow-up Questions

No. Path effort is the largest single adjacent difference along the route.

Graph

Read Similar Blogs

Graph

Disjoint Set Union: Union by Rank, Size and Path Compression

tuf-examples-1 Input: N = 5 , operations = [unionByRank(1,2), unionByRank(2,3), find(1,3), find(1,5)] Output: [true, false] Explanation: Rank-based merges place nodes 1 , 2 , and 3 in one set. Node...

89.1k
Graph

Dijkstra’s Algorithm

Given an undirected weighted graph with V vertices numbered from 0 to V - 1 , an edge list, and a source vertex, find the shortest distance from source to every vertex. Every edge appears as [u, v,...

93k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weight is positive...

96.1k
Comments0