Path With Minimum Effort

35 min · minimumEffortPath()

A hiking route is judged by its roughest step, not by the sum of all its climbs.

You receive a rectangular grid heights. Start at the top-left cell and reach the bottom-right cell by moving up, down, left, or right. The effort of a path is the largest absolute height difference across any single move on that path.

Return the smallest effort achievable by any valid path. A one-cell hike takes no moves, so its effort is 0.

Constraints

1 <= heights.length <= 100
1 <= heights[i].length <= 100
Every row has the same length.
1 <= heights[row][col] <= 1_000_000

Hints

Change what distance means

Reaching a cell with effort e means the roughest step so far is e. Crossing an edge of size d changes that route's effort to max(e, d), not e + d.

Dijkstra still fits

Keep the smallest known effort for each cell in a min-heap. Pop the route with the lowest current effort and relax its four neighbors using that max rule.

Another lens: can you cross?

For a guessed effort limit, BFS can test whether the destination is reachable using only steps at or below that limit. Reachability is monotonic, so binary search works.

Follow-up

How would the result change if diagonal moves were allowed too? Which part of your algorithm would need to change?

Visible cases

Examples

Example 1

ready

Input: heights = [ [ 1, 2, 2 ], [ 3, 8, 2 ], [ 5, 3, 5 ] ]
Expected: 2
Why: a route along the left and bottom keeps every step at 2 or less

Example 2

ready

Input: heights = [ [ 1, 2, 3 ], [ 3, 8, 4 ], [ 5, 3, 5 ] ]
Expected: 1
Why: the outer route changes height by at most 1 per move

Example 3

ready

Input: heights = [ [ 7 ] ]
Expected: 0
Why: one cell needs no movement

Interview signal

Asked at

AmazonGoogle

Binary search + BFS — ask whether an effort is enough

Suppose you guess an effort limit L. Breadth-first search can walk only across edges whose height difference is at most L. If it reaches the destination, every larger limit also works; if it fails, every smaller limit fails too.

Binary search is the right outer algorithm because that reachability answer is monotonic — once it becomes true, it stays true. BFS is the right inner algorithm because all allowed grid moves count equally when you're checking connectivity.

from collections import deque
 
 
def minimum_effort_path(heights: list[list[int]]) -> int:
    rows, cols = len(heights), len(heights[0])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 
    def can_reach(limit: int) -> bool:
        queue = deque([(0, 0)])
        seen = {(0, 0)}
        while queue:
            row, col = queue.popleft()
            if (row, col) == (rows - 1, cols - 1):
                return True
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if not (0 <= nr < rows and 0 <= nc < cols) or (nr, nc) in seen:
                    continue
                if abs(heights[row][col] - heights[nr][nc]) <= limit:
                    seen.add((nr, nc))
                    queue.append((nr, nc))
        return False
 
    low, high = 0, 1_000_000 - 1
    while low < high:
        middle = (low + high) // 2
        if can_reach(middle):
            high = middle
        else:
            low = middle + 1
    return low

Time O(mn log H), where H is the height range: each binary-search step runs one grid BFS. Space O(mn) for the queue and visited cells.

Minimax Dijkstra — finalize the gentlest route

Ordinary shortest paths add edge weights. Here a route's cost is the maximum edge seen so far. The relaxation rule becomes:

candidate = max(effort_so_far, current_step_difference)

Dijkstra is the right choice because this minimax cost never decreases as a route grows. The heap always exposes the unfinished cell with the smallest possible current effort, and the first time the destination is popped, that effort is final.

import heapq
 
 
def minimum_effort_path(heights: list[list[int]]) -> int:
    rows, cols = len(heights), len(heights[0])
    efforts = [[float("inf")] * cols for _ in range(rows)]
    efforts[0][0] = 0
    queue = [(0, 0, 0)]
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 
    while queue:
        effort, row, col = heapq.heappop(queue)
        if (row, col) == (rows - 1, cols - 1):
            return effort
        if effort != efforts[row][col]:
            continue
 
        for dr, dc in directions:
            nr, nc = row + dr, col + dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            step = abs(heights[row][col] - heights[nr][nc])
            candidate = max(effort, step)
            if candidate < efforts[nr][nc]:
                efforts[nr][nc] = candidate
                heapq.heappush(queue, (candidate, nr, nc))
 
    return 0

The shape is Dijkstra; only the definition of path cost changed. That is the reusable idea: prove the cost can't improve by extending a path, then let the heap finalize the best frontier state.

Time O(mn log(mn)) because each cell enters a heap over at most mn cells. Space O(mn) for the effort table and heap.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrayheights: int[][]

Expected

Run: visible + custom · Submit: full suite