Minimum Effort Path — Dijkstra or Binary Search + BFS

Problem Statement

LeetCode 1631 — Path With Minimum Effort (Medium)

You are given an m x n grid of integers heights where heights[i][j] represents the elevation at cell (i, j). A path's effort is defined as the maximum absolute difference in heights between any two consecutive cells on that path. Return the minimum effort required to travel from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1).

Constraints:

1 <= m, n <= 100
1 <= heights[i][j] <= 10^6

Example 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: Path [1,3,5,3,5] has maximum absolute difference 2.
             Other paths are worse:
             [1,2,2,2,5] → effort = 3 (|2-5|)
             [1,2,8,3,5] → effort = 6 (|2-8|)

Example 2:

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: Path [1,2,3,4,5] goes right then down, max diff = 1.

Example 3:

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: There exists a path where all adjacent heights are equal.

Why This Problem Matters

This problem is a gateway to understanding how classic shortest-path algorithms generalize beyond "sum of weights" to other path aggregation functions. Standard Dijkstra minimizes the sum of edge weights. Here, we want to minimize the maximum edge weight encountered on any path — a different but structurally similar objective.

The problem appears in interviews at companies like Google, Amazon, and Meta as a test of whether you can:

Recognize that a "minimax path" problem maps naturally to a modified Dijkstra
Alternatively, identify the binary search + BFS approach as a clean feasibility-check pattern

Both approaches are valid and worth knowing. Dijkstra is optimal in complexity; binary search + BFS is often more intuitive to derive on the spot.

The same minimax path structure appears in:

LC 778 — Swim in Rising Water (almost identical)
LC 1514 — Path with Maximum Probability (maximize product)
Network reliability problems in distributed systems

The Core Insight

Dijkstra approach: Redefine the "distance" from source to cell (r, c) as the minimum effort to reach it. The effort to move from (r, c) to (nr, nc) is |heights[nr][nc] - heights[r][c]|. The effort of a path is the maximum single-step effort. Use a min-heap where the state is (current_max_effort, r, c). When extending a path, the new effort is max(current_effort, step_effort). Process cells in order of current effort — the first time you reach (m-1, n-1), that is the answer.

Binary search + BFS approach: The answer lies in the range [0, max_height - min_height]. Binary search on the effort threshold mid. For a given threshold, run BFS/DFS checking if you can reach (m-1, n-1) using only steps where |h1 - h2| <= mid. If reachable, try a smaller threshold; otherwise increase.

Both approaches exploit the fact that if effort E is achievable, any effort E' > E is also achievable (monotonicity), which makes binary search valid.

Visual Dry Run

heights = [[1,2,2],
           [3,8,2],
           [5,3,5]]
 
Dijkstra trace:
  Initial: heap = [(0, 0, 0)], dist[0][0] = 0
 
  Pop (0, 0, 0) — effort 0 at (0,0)
    Neighbor (0,1): step = |2-1| = 1, new_effort = max(0,1) = 1
      dist[0][1] = 1, push (1, 0, 1)
    Neighbor (1,0): step = |3-1| = 2, new_effort = max(0,2) = 2
      dist[1][0] = 2, push (2, 1, 0)
 
  Pop (1, 0, 1) — effort 1 at (0,1)
    Neighbor (0,0): skip (dist is smaller)
    Neighbor (0,2): step = |2-2| = 0, new_effort = max(1,0) = 1
      dist[0][2] = 1, push (1, 0, 2)
    Neighbor (1,1): step = |8-2| = 6, new_effort = max(1,6) = 6
      dist[1][1] = 6, push (6, 1, 1)
 
  Pop (1, 0, 2) — effort 1 at (0,2)
    Neighbor (1,2): step = |2-2| = 0, new_effort = max(1,0) = 1
      dist[1][2] = 1, push (1, 1, 2)
 
  Pop (1, 1, 2) — effort 1 at (1,2)
    Neighbor (2,2): step = |5-2| = 3, new_effort = max(1,3) = 3
      dist[2][2] = 3, push (3, 2, 2)
    Neighbor (0,2): skip
    Neighbor (1,1): step = |8-2| = 6, new_effort = max(1,6) = 6 — no improvement
 
  Pop (2, 1, 0) — effort 2 at (1,0)
    Neighbor (2,0): step = |5-3| = 2, new_effort = max(2,2) = 2
      dist[2][0] = 2, push (2, 2, 0)
    ...
 
  Pop (2, 2, 0) — effort 2 at (2,0)
    Neighbor (2,1): step = |3-5| = 2, new_effort = max(2,2) = 2
      dist[2][1] = 2, push (2, 2, 1)
 
  Pop (2, 2, 1) — effort 2 at (2,1)
    Neighbor (2,2): step = |5-3| = 2, new_effort = max(2,2) = 2
      dist[2][2] currently 3 > 2 → update! push (2, 2, 2)
 
  Pop (2, 2, 2) — effort 2 at (2,2) = destination → return 2
 
Answer: 2 ✓

Common Mistakes

Using sum instead of max for effort. The effort of a path is the maximum single-step difference, not the sum. Using new_effort = current + step gives incorrect results.
Not skipping stale heap entries. In Dijkstra, when you pop (d, r, c) and d > dist[r][c], skip it — a better path was already found. Without this check, you reprocess cells and get wrong updates.
Initializing all distances to 0 instead of infinity. dist should start at float('inf') for all cells except (0,0) which starts at 0. Starting all at 0 means no cell will ever be relaxed.
Binary search bounds wrong. The lower bound is 0 (all heights equal) and the upper bound is 10^6 - 1 (max difference given heights range). Using max(heights) as upper bound without considering the maximum possible difference can miss some cases.
BFS/DFS in the binary search branch forgetting to reset visited. Each call to canReach(mid) must use a fresh visited array. Reusing a stale visited from the previous iteration gives wrong feasibility results.
Missing the early exit when source equals destination. If m == 1 and n == 1, the grid has a single cell and the answer is 0. Dijkstra handles this naturally, but some BFS implementations may loop.

Solutions

Python — Dijkstra (Optimal)

import heapq
 
class Solution:
    def minimumEffortPath(self, heights: list[list[int]]) -> int:
        R, C = len(heights), len(heights[0])    # grid dimensions
 
        # dist[r][c] = minimum effort to reach (r,c) from (0,0)
        dist = [[float('inf')] * C for _ in range(R)]
        dist[0][0] = 0                           # start cell has zero effort
 
        # min-heap: (current_max_effort, row, col)
        heap = [(0, 0, 0)]
 
        while heap:
            d, r, c = heapq.heappop(heap)        # pop lowest-effort cell
 
            # skip stale heap entries
            if d > dist[r][c]:
                continue
 
            # reached destination — return minimum effort found
            if r == R - 1 and c == C - 1:
                return d
 
            # explore all 4 neighbors
            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < R and 0 <= nc < C:
                    # effort for this step = absolute height difference
                    step_effort = abs(heights[nr][nc] - heights[r][c])
                    # path effort = max of all steps (minimax objective)
                    new_effort = max(d, step_effort)
                    # only update if we found a better path to (nr, nc)
                    if new_effort < dist[nr][nc]:
                        dist[nr][nc] = new_effort
                        heapq.heappush(heap, (new_effort, nr, nc))
 
        return 0    # unreachable given valid input (connected grid)

Python — Binary Search + BFS

from collections import deque
 
class Solution:
    def minimumEffortPath(self, heights: list[list[int]]) -> int:
        R, C = len(heights), len(heights[0])
 
        def canReach(effort):
            # BFS: can we go from (0,0) to (R-1,C-1) with max step <= effort?
            visited = [[False] * C for _ in range(R)]
            visited[0][0] = True
            q = deque([(0, 0)])
            while q:
                r, c = q.popleft()
                if r == R - 1 and c == C - 1:
                    return True                   # reached destination
                for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc]:
                        # only traverse if step effort is within budget
                        if abs(heights[nr][nc] - heights[r][c]) <= effort:
                            visited[nr][nc] = True
                            q.append((nr, nc))
            return False                          # destination unreachable
 
        # binary search on the answer: effort in [0, 10^6]
        lo, hi = 0, 10 ** 6
        while lo < hi:
            mid = (lo + hi) // 2
            if canReach(mid):
                hi = mid                          # mid works; try smaller
            else:
                lo = mid + 1                      # mid too small; increase
 
        return lo                                 # smallest feasible effort

JavaScript — Dijkstra

/**
 * @param {number[][]} heights
 * @return {number}
 */
var minimumEffortPath = function(heights) {
    const R = heights.length;
    const C = heights[0].length;
 
    // dist[r][c] = best (minimum) effort to reach (r,c)
    const dist = Array.from({ length: R }, () => Array(C).fill(Infinity));
    dist[0][0] = 0;
 
    // min-heap: [effort, row, col]
    // Using a simple array sorted on insert (priority queue simulation)
    const heap = [[0, 0, 0]];
 
    // Min-heap helpers
    function heapPush(heap, item) {
        heap.push(item);
        heap.sort((a, b) => a[0] - b[0]);  // sort by effort ascending
    }
 
    while (heap.length > 0) {
        const [d, r, c] = heap.shift();    // pop minimum effort item
 
        // skip stale entries
        if (d > dist[r][c]) continue;
 
        // reached destination
        if (r === R - 1 && c === C - 1) return d;
 
        // explore 4 neighbors
        for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
            const nr = r + dr;
            const nc = c + dc;
            if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
                // step effort = absolute height difference
                const stepEffort = Math.abs(heights[nr][nc] - heights[r][c]);
                // path effort = maximum single-step effort on path
                const newEffort = Math.max(d, stepEffort);
                // relax if better
                if (newEffort < dist[nr][nc]) {
                    dist[nr][nc] = newEffort;
                    heapPush(heap, [newEffort, nr, nc]);
                }
            }
        }
    }
 
    return 0;  // unreachable for valid input
};

Complexity Analysis

Approach	Time Complexity	Space Complexity
Dijkstra	O(m * n * log(m * n))	O(m * n)
Binary Search + BFS	O(m * n * log(max_height))	O(m * n)

Dijkstra Time: Each cell is pushed to the heap at most once per neighbor (bounded by 4 * m * n). Each heap operation costs O(log(m * n)). Total: O(m * n * log(m * n)).
Binary Search + BFS: BFS runs in O(m * n). Binary search runs O(log(10^6)) = O(20) iterations. Total: O(20 * m * n) = O(m * n * log(max_height)).
Space: Both use O(m * n) for the dist/visited array and the heap/queue.

In practice, Dijkstra is faster since log(m * n) is typically smaller than log(max_height) for small grids, and Dijkstra avoids running BFS multiple times.

Follow-up Questions

Maximize instead of minimize: LC 1514 — Path with Maximum Probability uses the same Dijkstra structure but with a max-heap and multiplicative edge weights.
Swim in Rising Water (LC 778): Essentially the same problem — the effort is the maximum height on the path rather than the maximum height difference.
What if we allow revisiting cells? Dijkstra already handles this correctly — it finds the globally optimal path regardless of path length.
What if the grid has negative heights? The absolute difference is always non-negative so Dijkstra still works. There are no negative edge weights in this problem.
Parallel shortest paths: If you need the k-th minimum effort path, use a modified Dijkstra that allows k visits per cell.

This Pattern Solves

LC 778 — Swim in Rising Water: Minimax path (max cell value) — same Dijkstra structure
LC 1514 — Path with Maximum Probability: Maximax path (max product) — max-heap Dijkstra
Any "minimize the worst-case step" routing problem in weighted grids or graphs

Key Takeaways

Minimum Effort Path uses Dijkstra where "distance" = max absolute height difference along the path — replace sum with max in relaxation
Any monotonically non-decreasing path aggregation (sum, max, product of values) can be optimized with Dijkstra
Relaxation condition: max(curr_effort, abs(height_diff)) < best[nr][nc]
Use lazy deletion: push duplicate entries and skip stale ones when popping from the min-heap
Binary search on the answer + BFS is an alternative O(m*n log(max_val)) approach
Time O(mn log(mn)) with a heap; Space O(m*n) for the distance grid and heap entries
This custom-aggregation Dijkstra pattern applies to LC 778, LC 1368, and any min-max path problem on grids

Problem Statement#

Why This Problem Matters#

The Core Insight#

Visual Dry Run#

Common Mistakes#

Solutions#

Python — Dijkstra (Optimal)#

Python — Binary Search + BFS#

JavaScript — Dijkstra#

Complexity Analysis#

Follow-up Questions#

This Pattern Solves#

Key Takeaways#

Related reading