Path With Minimum Effort
Understanding the Problem
This looks like a standard shortest-path problem on a grid, but the cost of a path is defined differently. The cost is not the sum of edge weights. It is the maximum edge weight along the entire path. That difference changes which algorithm applies.
Each cell has a height, and moving between adjacent cells costs effort equal to the absolute height difference. The effort of a route is the single largest step it contains, not the total of all steps. The goal is a path from the top-left to the bottom-right that minimizes this largest step.
This is a "minimize the maximum" objective, also called a bottleneck path problem. Standard Dijkstra minimizes a sum of edge weights, so it does not apply directly. Two approaches fit a bottleneck metric: a modified Dijkstra that tracks the maximum edge weight on the path instead of the cumulative cost, and binary search on the answer paired with a BFS reachability check.
Key Constraints:
1 <= rows, columns <= 100→ The grid has at most 10,000 cells and roughly 40,000 directed edges. A heap-based Dijkstra running in O(V log V) over this many cells is well within time limits.1 <= heights[i][j] <= 10^6→ Heights range up to a million, so the largest possible effort is 999,999. The effort fits in a 32-bit integer, and it gives a binary search range of [0, 999999].
Approach 1: Binary Search + BFS
Intuition
Fix a candidate effort limit k. Whether the destination is reachable using only steps of size at most k is a plain reachability question: run BFS from the top-left, and from each cell move only to neighbors whose height difference is at most k. If BFS reaches the bottom-right cell, then k is an achievable effort.
The reachability check is monotonic in k. If a value k allows a valid path, then any value larger than k allows the same path, since it permits every step k did and possibly more. So the set of achievable efforts is an interval [answer, 999999], and the answer is its smallest member. That monotonicity is what makes binary search valid: probe a midpoint, and if it is reachable, search lower; otherwise search higher.
This decomposes the problem into two parts, a binary search for the threshold and a BFS for reachability, each of which is straightforward on its own.
Algorithm
- Set
low = 0andhigh = 10^6(the maximum possible height difference). - While
low < high: - Compute
mid = (low + high) / 2. - Run BFS from
(0, 0). Only move to adjacent cells where|heights[curr] - heights[neighbor]| <= mid. - If BFS reaches
(rows-1, columns-1), sethigh = mid(this effort is achievable, try smaller). - Otherwise, set
low = mid + 1(need more effort). - Return
low.
Example Walkthrough
Code
- Time Complexity: O(m n log(maxHeight)). The binary search runs for ~20 iterations. Each iteration runs a BFS that visits all m * n cells.
- Space Complexity: O(m n). The visited array and BFS queue each use O(m n) space.
This runs a full BFS for every binary search iteration, around 20 in total. The next approach uses the height differences directly and finds the answer in a single graph traversal, with no outer binary search.
Approach 2: Modified Dijkstra's Algorithm (Optimal)
Intuition
Standard Dijkstra tracks the cumulative distance to each node and always processes the node with the smallest total distance. For a bottleneck path, the only change is the cost function: instead of summing edge weights, track the maximum edge weight along the path to each cell.
For each cell, effort[r][c] holds the smallest possible bottleneck (the smallest "largest step") over all paths from (0, 0) to that cell. Extending a path to a neighbor gives a candidate effort of max(effort[r][c], |heights[r][c] - heights[nr][nc]|), since the new path's bottleneck is the larger of the current path's bottleneck and the new step. If that candidate is smaller than the neighbor's recorded effort, update it and push the neighbor onto the priority queue.
The greedy choice is safe because effort along a path never decreases as the path grows: appending an edge takes the max of the current bottleneck and the new edge, so it can only hold steady or rise. When the min-heap pops a cell, every alternative still in the heap has an effort at least as large, and any path discovered later must pass through one of those cells, so it cannot reach this cell with a smaller bottleneck. The popped effort is therefore final, which is the same argument that makes standard Dijkstra correct under a non-negative cost rule.
Algorithm
- Create a 2D array
effortinitialized to infinity, witheffort[0][0] = 0. - Push
(0, 0, 0)into a min-heap (effort, row, col). - While the heap is not empty:
- Pop the cell
(e, r, c)with the smallest effort. - If
(r, c)is the destination, returne. - If
e > effort[r][c], skip (we've already found a better path). - For each neighbor
(nr, nc): - Compute
newEffort = max(e, |heights[r][c] - heights[nr][nc]|). - If
newEffort < effort[nr][nc], updateeffort[nr][nc] = newEffortand push to the heap. - Return
effort[rows-1][cols-1].
Example Walkthrough
Code
- Time Complexity: O(m n log(m n)). Each cell can be pushed to the heap at most 4 times. With m n cells, each heap operation takes O(log(m * n)).
- Space Complexity: O(m n). The effort array and heap both use O(m n) space.