Path With Minimum Effort: Binary Search on the Answer

Path With Minimum Effort is LeetCode 1631. You are given a 2D grid of heights, and you need to find a path from the top-left corner to the bottom-right corner that minimizes the "effort." The effort of a path is defined as the maximum absolute difference in heights between two consecutive cells along that path. This problem is a great example of binary search on the answer combined with BFS reachability, and once you see the pattern, it applies to a whole family of similar problems.

The problem

You have an m x n grid called heights where heights[r][c] represents the height of cell (r, c). You want to travel from (0, 0) to (m-1, n-1). In each step, you can move up, down, left, or right to an adjacent cell. A path's effort is the maximum absolute difference in heights between two consecutive cells along the path. Find a path that minimizes this effort.

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

The optimal path goes 1 -> 3 -> 5 -> 3 -> 1 along the top row and then down. Every step has a height difference of exactly 2, so the effort is max(2, 2, 2, 2) = 2. No path can do better.

The brute force approach

You could try every possible path from (0, 0) to (m-1, n-1) and track the minimum effort across all of them. But the number of paths in a grid grows exponentially. Even with memoization, the state space is enormous because the "effort so far" is part of the state. This approach is far too slow for any reasonable grid size.

The key insight

Instead of searching for a path directly, you flip the question: "Given an effort threshold mid, can I reach the bottom-right from the top-left using only steps where the height difference is at most mid?" That is a simple BFS or DFS reachability check. Binary search finds the smallest mid where the answer is "yes."

Step-by-step walkthrough

Let's walk through the binary search on the example grid [[1,3,5],[2,8,3],[4,2,1]]. The maximum possible difference between any two adjacent cells is 7 (between 1 and 8), so we search the range [0, 7].

Only four iterations of binary search, each running a quick BFS. Instead of enumerating all paths, we checked four effort thresholds and zeroed in on the answer.

The code

from collections import deque

class Solution:
    def minimumEffortPath(self, heights):
        rows, cols = len(heights), len(heights[0])

        def can_reach(effort):
            visited = [[False] * cols for _ in range(rows)]
            queue = deque([(0, 0)])
            visited[0][0] = True
            while queue:
                r, c = queue.popleft()
                if r == rows - 1 and c == cols - 1:
                    return True
                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]:
                        if abs(heights[nr][nc] - heights[r][c]) <= effort:
                            visited[nr][nc] = True
                            queue.append((nr, nc))
            return False

        lo, hi = 0, 10**6
        while lo < hi:
            mid = (lo + hi) // 2
            if can_reach(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

Let's walk through the important decisions.

can_reach(effort) is the feasibility function. It runs BFS from (0, 0), only stepping to neighbors where the absolute height difference is at most effort. If BFS reaches (rows-1, cols-1), the threshold is feasible.

lo = 0, hi = 10**6. The minimum possible effort is 0 (all cells the same height). The maximum is bounded by the constraint that heights go up to 10^6. You could also compute the actual max difference in the grid, but using 10^6 is simpler and only adds a few extra binary search iterations.

while lo < hi, not while lo <= hi. We are narrowing down to a single answer. When lo == hi, that is our answer.

if can_reach(mid): hi = mid. If the current effort works, it might be the answer, or a smaller effort might also work. So we keep mid in the range and search left.

else: lo = mid + 1. If the current effort does not work, we need strictly more. Move lo past mid.

Complexity analysis

Time for binary search + BFS: the binary search runs O(log(maxDiff)) iterations, where maxDiff is the range of possible efforts (up to 10^6, so about 20 iterations). Each iteration runs BFS in O(m * n). Total: O(m * n * log(maxDiff)).

Space: O(m * n) for the visited array in BFS.

The building blocks

Binary search on the answer

The core technique here is the same one used in Koko Eating Bananas, Capacity to Ship Packages, and Split Array Largest Sum. You have a range of candidate answers, a feasibility function that is monotonic over that range, and you binary search for the boundary.

The template:

lo, hi = min_possible, max_possible
while lo < hi:
    mid = (lo + hi) // 2
    if is_feasible(mid):
        hi = mid
    else:
        lo = mid + 1
return lo

The only thing that changes between problems is the feasibility function. Here it is a BFS reachability check. In Koko Eating Bananas it is a sum of ceiling divisions. The binary search shell stays identical.

BFS reachability with a constraint

The can_reach function is a standard BFS with one twist: you only enqueue a neighbor if the edge weight (height difference) is within the allowed threshold. This "constrained BFS" pattern shows up whenever you need to check whether a path exists under some restriction.

def can_reach(effort):
    visited = [[False] * cols for _ in range(rows)]
    queue = deque([(0, 0)])
    visited[0][0] = True
    while queue:
        r, c = queue.popleft()
        if r == rows - 1 and c == cols - 1:
            return True
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if in_bounds(nr, nc) and not visited[nr][nc]:
                if abs(heights[nr][nc] - heights[r][c]) <= effort:
                    visited[nr][nc] = True
                    queue.append((nr, nc))
    return False

The structure is identical to any grid BFS. The only addition is the if abs(...) <= effort guard on the edge.

Edge cases

• 1x1 grid: start and end are the same cell. The answer is 0 with no steps needed.
• All cells have the same height: every step has difference 0, so the answer is 0.
• Single row or single column: there is only one path. The effort is the max consecutive difference along that path.
• Two cells: [[1, 10]]. The answer is abs(10 - 1) = 9. No choice but to take the one step.
• Large flat grid with one spike: BFS will route around the spike if possible. The binary search naturally finds the threshold that avoids it.

From understanding to recall

The idea is clean: binary search on the effort, BFS to check feasibility. You probably get it right now. But writing it under pressure is another story. Was it lo < hi or lo <= hi? Do you set hi = mid or hi = mid - 1? Do you mark visited before or after enqueueing?

These details matter, and they are exactly the kind of thing that slips when you are nervous. Spaced repetition is how you lock them in. You write the binary search shell from scratch, then the BFS feasibility check, then the full solution. After a few rounds at increasing intervals, the pattern is automatic. You see "minimize the maximum" in a problem statement, and the template flows out without hesitation.

Related posts

• Swim in Rising Water - Another grid problem where you minimize the maximum value along a path, solvable with binary search + BFS or Dijkstra
• Shortest Path in Binary Matrix - BFS on a grid to find the shortest path, the same traversal pattern used in our feasibility check
• Koko Eating Bananas - The classic binary search on the answer problem, using the same while lo < hi template with a different feasibility function