Log inSign up
mediumLeetCodeNot Started

Path With Minimum Effort

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the *minimum effort* required to travel from the top-left cell to the bottom-right cell.

Constraints:

  • rows == heights.length
  • columns == heights[i].length
  • 1 <= rows, columns <= 100
  • 1 <= heights[i][j] <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Differentiate standard additive shortest path from minimax bottleneck shortest path.
  • Adapt Dijkstra's algorithm to bottleneck edge weight relaxation.
  • Formulate decision problems with Binary Search on Answer + BFS traversal.
  • Analyze time and space complexity across grid graph representations.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever a path problem asks to 'minimize the maximum step cost' (minimax), think of two approaches: Modified Dijkstra with min-heap, or Binary Search on the answer combined with BFS/DFS reachability.

1. DFS Backtracking with Pruning

Intuition

Explore all possible 4-directional simple paths from (0, 0) to (R-1, C-1). Track the maximum step difference along each path. Maintain a 2D array minEffort[r][c] to prune any branch whose current effort exceeds the best recorded effort to reach (r, c).

Algorithm

  1. Initialize minEffort grid of size R × C with infinity, set minEffort[0][0] = 0.
  2. Define dfs(r, c, currentMax):
  3. If currentMax >= minEffort[r][c], prune branch.
  4. minEffort[r][c] = currentMax.
  5. If r == R - 1 && c == C - 1, return.
  6. For each 4-directional neighbor (nr, nc):
  7. stepDiff = abs(heights[nr][nc] - heights[r][c])
  8. dfs(nr, nc, max(currentMax, stepDiff))
  9. Return minEffort[R-1][C-1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <cmath>
5#include <climits>
6
7const int dr[] = {-1, 1, 0, 0};
8const int dc[] = {0, 0, -1, 1};
9
10void dfs(int r, int c, int currentEffort, const std::vector<std::vector<int>>& heights,
11 std::vector<std::vector<int>>& minEffort) {
12 if (currentEffort >= minEffort[r][c]) return;
13 minEffort[r][c] = currentEffort;
14
15 int R = heights.size(), C = heights[0].size();
16 if (r == R - 1 && c == C - 1) return;
17
18 for (int i = 0; i < 4; ++i) {
19 int nr = r + dr[i], nc = c + dc[i];
20 if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
21 int stepDiff = std::abs(heights[nr][nc] - heights[r][c]);
22 dfs(nr, nc, std::max(currentEffort, stepDiff), heights, minEffort);
23 }
24 }
25}
26
27int minimumEffortPathDFS(std::vector<std::vector<int>>& heights) {
28 int R = heights.size(), C = heights[0].size();
29 std::vector<std::vector<int>> minEffort(R, std::vector<int>(C, INT_MAX));
30 dfs(0, 0, 0, heights, minEffort);
31 return minEffort[R - 1][C - 1];
32}
33
34int main() {
35 std::vector<std::vector<int>> heights = {{1,2,2},{3,8,2},{5,3,5}};
36 std::cout << "Min Effort (DFS): " << minimumEffortPathDFS(heights) << std::endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(4^(R * C)) in the worst case due to exhaustive exploration of all grid paths.
  • Space complexity: O(R * C) for the recursion stack and effort matrix.

2. Binary Search on Answer + BFS

Intuition

Notice the monotonicity of the problem: if target effort M allows reaching the destination, then any effort M' > M also allows it. The possible effort lies between 0 and 106. We binary search for M \in [0, 106]. In each verification step, run BFS from (0, 0) only traversing edges where |h_1 - h_2| <= M.

Algorithm

  1. Set low = 0, high = 10^6, ans = high.
  2. While low <= high:
  3. mid = low + (high - low) / 2
  4. Run BFS from (0, 0) using only adjacent moves with abs(heights[nr][nc] - heights[r][c]) <= mid.
  5. If destination (R-1, C-1) is reachable:
  6. ans = mid, high = mid - 1 (try smaller effort)
  7. Else:
  8. low = mid + 1 (need more effort)
  9. Return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <cmath>
5
6bool canReach(int maxEffort, const std::vector<std::vector<int>>& heights) {
7 int R = heights.size(), C = heights[0].size();
8 std::vector<std::vector<bool>> visited(R, std::vector<bool>(C, false));
9 std::queue<std::pair<int, int>> q;
10 q.push({0, 0});
11 visited[0][0] = true;
12
13 int dr[] = {-1, 1, 0, 0};
14 int dc[] = {0, 0, -1, 1};
15
16 while (!q.empty()) {
17 auto [r, c] = q.front();
18 q.pop();
19 if (r == R - 1 && c == C - 1) return true;
20
21 for (int i = 0; i < 4; ++i) {
22 int nr = r + dr[i], nc = c + dc[i];
23 if (nr >= 0 && nr < R && nc >= 0 && nc < C && !visited[nr][nc]) {
24 if (std::abs(heights[nr][nc] - heights[r][c]) <= maxEffort) {
25 visited[nr][nc] = true;
26 q.push({nr, nc});
27 }
28 }
29 }
30 }
31 return false;
32}
33
34int minimumEffortPathBinarySearch(std::vector<std::vector<int>>& heights) {
35 int low = 0, high = 1000000, ans = high;
36 while (low <= high) {
37 int mid = low + (high - low) / 2;
38 if (canReach(mid, heights)) {
39 ans = mid;
40 high = mid - 1;
41 } else {
42 low = mid + 1;
43 }
44 }
45 return ans;
46}
47
48int main() {
49 std::vector<std::vector<int>> heights = {{1,2,2},{3,8,2},{5,3,5}};
50 std::cout << "Min Effort (BS): " << minimumEffortPathBinarySearch(heights) << std::endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(R * C * log(max_height)) where max_height = 10^6, so log2(10^6) ~ 20 checks of O(R * C) BFS.
  • Space complexity: O(R * C) for the BFS queue and visited array.

3. Modified Dijkstra's Algorithm (Minimax Shortest Path)

Intuition

Model each cell (r, c) as a graph vertex. An edge to an adjacent cell (nr, nc) has weight |heights[nr][nc] - heights[r][c]|. By using a priority queue ordered by effort, when cell (r, c) is popped from the min-heap, its minimal bottleneck effort is finalized. The relaxation step computes newEffort = max(currentEffort, abs(heights[nr][nc] - heights[r][c])) and updates effort[nr][nc] if newEffort < effort[nr][nc].

Algorithm

  1. Initialize effort matrix of size R × C with infinity, set effort[0][0] = 0.
  2. Push (0, 0, 0) (effort 0, row 0, col 0) into min-heap.
  3. While min-heap is not empty:
  4. Pop (eff, r, c).
  5. If r == R - 1 && c == C - 1, return eff (first arrival via min-heap is optimal).
  6. If eff > effort[r][c], continue (stale entry).
  7. For each 4-directional neighbor (nr, nc):
  8. nextEffort = max(eff, abs(heights[nr][nc] - heights[r][c]))
  9. If nextEffort < effort[nr][nc]:
  10. effort[nr][nc] = nextEffort
  11. Push (nextEffort, nr, nc) into min-heap.
  12. Return effort[R - 1][C - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <cmath>
5#include <climits>
6#include <tuple>
7
8int minimumEffortPath(std::vector<std::vector<int>>& heights) {
9 int R = heights.size(), C = heights[0].size();
10 std::vector<std::vector<int>> effort(R, std::vector<int>(C, INT_MAX));
11 // tuple: (effort, r, c)
12 std::priority_queue<std::tuple<int, int, int>, std::vector<std::tuple<int, int, int>>, std::greater<>> pq;
13
14 effort[0][0] = 0;
15 pq.push({0, 0, 0});
16
17 int dr[] = {-1, 1, 0, 0};
18 int dc[] = {0, 0, -1, 1};
19
20 while (!pq.empty()) {
21 auto [eff, r, c] = pq.top();
22 pq.pop();
23
24 if (r == R - 1 && c == C - 1) return eff;
25 if (eff > effort[r][c]) continue;
26
27 for (int i = 0; i < 4; ++i) {
28 int nr = r + dr[i], nc = c + dc[i];
29 if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
30 int nextEffort = std::max(eff, std::abs(heights[nr][nc] - heights[r][c]));
31 if (nextEffort < effort[nr][nc]) {
32 effort[nr][nc] = nextEffort;
33 pq.push({nextEffort, nr, nc});
34 }
35 }
36 }
37 }
38 return 0;
39}
40
41int main() {
42 std::vector<std::vector<int>> heights = {{1,2,2},{3,8,2},{5,3,5}};
43 std::cout << "Optimal Min Effort (Dijkstra): " << minimumEffortPath(heights) << std::endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(R * C log(R * C)) where V = R * C. Each grid cell has at most 4 edges, and heap operations take logarithmic time.
  • Space complexity: O(R * C) for the 2D effort matrix and min-heap storage.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS BacktrackingO(4^(R * C))O(R * C)Simple to write for tiny grids.Exponential time complexity; times out quickly.
2.Binary Search + BFSO(R * C * log(max_diff))O(R * C)Very predictable runtime; avoids complex priority queue logic.Requires multiple BFS passes over the entire grid.
3.Modified DijkstraOptimalO(R * C * log(R * C))O(R * C)Greedy single-pass search; terminates the moment destination is popped.Requires min-heap / priority queue implementation.

Common Pitfalls & Crucial Edge Cases

Summing edge weights instead of taking the maximum.

The problem defines effort as the maximum absolute difference along the route, not the total sum of differences.

Forgetting to skip stale priority queue entries with if (eff > effort[r][c]) continue;.

Skipping outdated heap items ensures the algorithm runs in strictly O(E log V).

Crucial Edge Cases to Validate:

  • 1x1 grid (rows = 1, cols = 1) — Algorithm immediately pops (0, 0) and returns 0 without exploring neighbors.
  • All cells have equal height — All step differences are 0; algorithm returns 0.
  • Strictly increasing / decreasing staircase grid — Dijkstra smoothly traverses adjacent unit steps, correctly computing the minimal height jumps.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify right away that this is a 'minimax path problem' (minimize the maximum edge weight).
  2. Explain both paradigms: Dijkstra's modified relaxation vs. Binary Search on Answer + BFS/DFS. Demonstrating both shows deep algorithmic versatility.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is Modified Dijkstra valid even though path costs are calculated using max() instead of addition?

2.If rows == 1 and columns == 1, what is the minimum effort?

3.In Binary Search on Answer, why can we safely set the initial upper bound to 106?

Back to DSA Sheet