Path With Minimum Effort

mediumAdvanced Graphs (Dijkstra / MST)203 stepsJava · Python · C++

A path's effort is its largest height difference between consecutive cells; find the path with the smallest effort. Dijkstra works with "cost = max edge so far" instead of a sum: always expand the cell with the smallest effort to reach it.

▶ Watch the animated trace

Traced input: heights = [[1, 2, 2], [3, 8, 2], [5, 3, 5]] → 2. Original problem: neetcode.io/problems/path-with-minimum-effort

Complexity

BestO(mn log mn)

AverageO(mn log mn)

WorstO(mn log mn)

SpaceO(mn)

Each cell can be pushed a few times.

Key idea

effort[r][c] = the smallest maximum step needed to reach (r, c).
Moving to a neighbour costs max(effort, |height difference|).
The first time the bottom-right is popped, its effort is final.
Binary search on the answer plus BFS is an alternative.

Common mistakes

Summing differences instead of taking the max.
Stopping when the target is first pushed rather than first popped.

Solution

Java

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
int minimumEffortPath(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    int[][] effort = new int[m][n];
    for (int[] row : effort) Arrays.fill(row, Integer.MAX_VALUE);
    effort[0][0] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    pq.offer(new int[]{0, 0, 0});
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int e = top[0], r = top[1], c = top[2];
        if (e > effort[r][c]) continue;
        if (r == m - 1 && c == n - 1) {
            return e;
        }
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
            int ne = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c]));
            if (ne < effort[nr][nc]) {
                effort[nr][nc] = ne;
                pq.offer(new int[]{ne, nr, nc});
            }
        }
    }
    return 0;
}

Python

# DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]: down, up, right, left
def minimumEffortPath(heights: List[List[int]]) -> int:
    m, n = len(heights), len(heights[0])
    effort = [[float("inf")] * n for _ in range(m)]
    effort[0][0] = 0
    heap = [(0, 0, 0)]
    while heap:
        e, r, c = heapq.heappop(heap)
        if e > effort[r][c]: continue
        if r == m - 1 and c == n - 1:
            return e
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n:
                ne = max(e, abs(heights[nr][nc] - heights[r][c]))
                if ne < effort[nr][nc]:
                    effort[nr][nc] = ne
                    heapq.heappush(heap, (ne, nr, nc))
    return 0

C++

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
int minimumEffortPath(vector<vector<int>>& heights) {
    int m = heights.size(), n = heights[0].size();
    vector<vector<int>> effort(m, vector<int>(n, INT_MAX));
    effort[0][0] = 0;
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
    pq.push({0, 0, 0});
    while (!pq.empty()) {
        auto [e, r, c] = pq.top(); pq.pop();
        if (e > effort[r][c]) continue;
        if (r == m - 1 && c == n - 1) {
            return e;
        }
        for (auto& d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
            int ne = max(e, abs(heights[nr][nc] - heights[r][c]));
            if (ne < effort[nr][nc]) {
                effort[nr][nc] = ne;
                pq.push({ne, nr, nc});
            }
        }
    }
    return 0;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single cell No moves needed.	`heights = [[7]]`	`0`
Flat grid Every step is free.	`heights = [[1, 1], [1, 1]]`	`0`
Single row No detour is possible, so the 1 → 10 jump is forced.	`heights = [[1, 10, 6, 7, 9, 10, 4, 9]]`	`9`