Path With Minimum Effort

NeetCode: Path With Minimum Effort · LeetCode: 1631. Path With Minimum Effort · Difficulty: Medium

You are given a rows x cols grid heights. Starting at the top-left cell, move up, down, left or right to reach the bottom-right cell. The effort of a route is the maximum absolute height difference between two consecutive cells on it. Return the minimum effort over all routes.

Example

Text

Input:  heights = [[1,2,2],[3,8,2],[5,3,5]]    Output: 2
Input:  heights = [[1,2,3],[3,8,4],[5,3,5]]    Output: 1
Input:  heights = [[7]]                         Output: 0

This is a shortest-path problem in which a path costs the maximum of its edge weights instead of their sum. The cost is monotone (extending a path never lowers it), which is what Dijkstra requires.

Brute force: sweep the grid relaxing until stable

Keep effort[r][c], the smallest known effort to reach each cell. Sweep over every cell and, for each neighbour, propose max(effort[cell], |height difference|); keep it if it is smaller. Repeat until a sweep changes nothing. This is Bellman-Ford style relaxation and may need many full sweeps.

The difference of two heights is an int, and Integer.MAX_VALUE marks "not reached yet". Very large heights would need long.

Java

import java.util.Arrays;

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length, cols = heights[0].length;
        int[][] effort = new int[rows][cols];
        for (int[] row : effort) Arrays.fill(row, Integer.MAX_VALUE);
        effort[0][0] = 0;
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (effort[r][c] == Integer.MAX_VALUE) continue;
                    for (int[] d : dirs) {
                        int nr = r + d[0], nc = c + d[1];
                        if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                        int cand = Math.max(effort[r][c], Math.abs(heights[r][c] - heights[nr][nc]));
                        if (cand < effort[nr][nc]) {
                            effort[nr][nc] = cand;
                            changed = true;
                        }
                    }
                }
            }
        }
        return effort[rows - 1][cols - 1];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minimumEffortPath(new int[][] {{1, 2, 2}, {3, 8, 2}, {5, 3, 5}}));
        System.out.println(s.minimumEffortPath(new int[][] {{1, 2, 3}, {3, 8, 4}, {5, 3, 5}}));
        System.out.println(s.minimumEffortPath(new int[][] {{7}}));
    }
}

Output

2
1
0

Time: O(P * m * n) where P is the number of sweeps (up to m * n in the worst case). Space: O(m * n).

Optimal: Dijkstra with a max-edge cost

Use a min-heap keyed by effort. The popped cell with the smallest effort has its final value, because any other route to it would have to pass through a heap entry that is at least as large. For each neighbour the new effort is max(current effort, step difference); push it if it improves the stored value. Each cell enters the heap a bounded number of times (once per improving edge), giving O(mn log mn).

Java's PriorityQueue is a min-heap. Each entry is an int[]{effort, row, column} ordered with Integer.compare on the effort.

Java

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length, cols = heights[0].length;
        int[][] effort = new int[rows][cols];
        for (int[] row : effort) Arrays.fill(row, Integer.MAX_VALUE);
        effort[0][0] = 0;
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.add(new int[] {0, 0, 0});
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int e = top[0], r = top[1], c = top[2];
            if (e > effort[r][c]) continue; // stale entry
            if (r == rows - 1 && c == cols - 1) return e;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                int cand = Math.max(e, Math.abs(heights[r][c] - heights[nr][nc]));
                if (cand < effort[nr][nc]) {
                    effort[nr][nc] = cand;
                    heap.add(new int[] {cand, nr, nc});
                }
            }
        }
        return 0;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minimumEffortPath(new int[][] {{1, 2, 2}, {3, 8, 2}, {5, 3, 5}}));
        System.out.println(s.minimumEffortPath(new int[][] {{1, 2, 3}, {3, 8, 4}, {5, 3, 5}}));
        System.out.println(s.minimumEffortPath(new int[][] {{7}}));
    }
}

Output

2
1
0

Time: O(m * n * log(m * n)). Space: O(m * n).