Coding interview problems › Graphs & Grids

🗺️ Graphs & Grids Medium

Path With Minimum Effort

Path With Minimum Effort explained: Dijkstra on a grid where a path costs its biggest height jump. Tested Python code, the min-max twist and a live visual.

Also searched as: minimum effort path in a grid · Dijkstra on a grid with max edge cost

🧭

Try it live Free

Dijkstra's Shortest Path

In the Dijkstra lab, watch the nearest unsettled node get settled first; here the distance being minimised is the steepest step so far instead of a sum.

Also useful: Binary Search, Number of Islands & Grid BFS

Open the playground →

The problem

You are given a grid of heights. Moving between adjacent cells (up, down, left, right) costs the absolute height difference. A path's effort is the largest single step cost along it. Return the minimum effort needed to go from the top-left to the bottom-right cell.

Inputheights = [[1,2,2],[3,8,2],[5,3,5]]
Output2

1 -> 3 -> 5 -> 3 -> 5 never climbs more than 2 in one step.

The key insight

This is a shortest-path problem where a path's cost is the maximum step, not the sum. Dijkstra still works because extending a path can never make its maximum smaller. Store for each cell the best effort to reach it, and when relaxing a neighbour use max(current effort, step cost) instead of addition.

Brute force first: Binary search on the effort and run a BFS that only takes steps within it: O(m·n·log H), a valid alternative worth mentioning.

Step-by-step approach

  1. Set best[0][0] = 0 and infinity elsewhere; push (0, 0, 0) onto a min-heap.
  2. Pop the cell with the smallest effort. If it is the target, return the effort.
  3. Skip the entry if it is stale (larger than the stored best).
  4. For each neighbour, compute e = max(effort, abs(height difference)).
  5. If e beats the neighbour's best, update it and push the neighbour.

Python solution

PYTHON 3tested
import heapq


def minimum_effort_path(heights):
    rows, cols = len(heights), len(heights[0])
    best = [[float("inf")] * cols for _ in range(rows)]
    best[0][0] = 0
    heap = [(0, 0, 0)]                 # effort, row, col
    while heap:
        eff, r, c = heapq.heappop(heap)
        if (r, c) == (rows - 1, cols - 1):
            return eff
        if eff > best[r][c]:
            continue                   # stale entry
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols:
                e = max(eff, abs(heights[nr][nc] - heights[r][c]))
                if e < best[nr][nc]:
                    best[nr][nc] = e
                    heapq.heappush(heap, (e, nr, nc))
    return 0

Complexity

TimeO(m·n·log(m·n))
SpaceO(m·n)

There are m·n cells with up to 4 edges each, and every heap operation costs O(log(m·n)). The best-effort grid and heap are O(m·n).

Common mistakes

Frequently asked questions

What is the time and space complexity of Path With Minimum Effort?

O(m·n·log(m·n)) time with Dijkstra on an m by n grid, and O(m·n) space for the effort grid and the heap.

Why is Dijkstra still correct when cost is a maximum?

Dijkstra needs a path's cost never to decrease when you extend it. max(effort, step) is never smaller than effort, so once a cell is popped with the smallest effort, no later path can beat it.

What other approaches work?

Binary search on the answer with a BFS or DFS feasibility check, or sort all edges by cost and add them with Union-Find until the start and end connect. All are accepted.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Graphs & Grids Graph Search: BFS vs DFS lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.