Problem statement

You are hiking across a terrain grid heights, starting at the top-left cell and aiming for the bottom-right cell, moving up, down, left or right.

A route's effort is the maximum absolute height difference between two consecutive cells on it. Return the minimum effort of any route.

Example 1

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

Example 2

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

Example 3

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0

Constraints

• 1 <= heights.length, heights[i].length <= 12
• 1 <= heights[i][j] <= 1000000

Follow-up: Binary search on the answer gives O(mn log C). A Dijkstra variant reaches the same bound without the search.

Hints for Path With Minimum Effort

1. Hint 1

   Ask a simpler question first: given a limit, is the destination reachable using only steps within it?

2. Hint 2

   That is a plain flood fill, so binary search the limit.

3. Hint 3

   Alternatively, run Dijkstra where a path's cost is the maximum edge rather than the sum.

How to solve Path With Minimum Effort

Binary search the effort limit: for a given limit, a flood fill using only steps with height difference ≤ limit tells whether the destination is reachable.

Approach

1. lo = 0, hi = max height.
2. While lo < hi: test mid with a DFS; if reachable, hi = mid, else lo = mid + 1.
3. Return lo.

Why it works

Reachability is monotone in the limit (a larger limit permits every step a smaller one does), so the smallest feasible limit can be found by bisection.

Complexity

• Time — O(m · n · log(maxHeight))
• Space — O(m · n)

Pitfalls

• Dijkstra with cost = max(edge) is the alternative; both are standard.

Reference solution

Python

def minimumEffortPath(heights) -> int:
    rows, cols = len(heights), len(heights[0])

    def reachable(limit):
        seen = [[False] * cols for _ in range(rows)]
        seen[0][0] = True
        stack = [(0, 0)]
        while stack:
            r, c = stack.pop()
            if r == rows - 1 and c == cols - 1:
                return True
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and not seen[nr][nc]:
                    if abs(heights[nr][nc] - heights[r][c]) <= limit:
                        seen[nr][nc] = True
                        stack.append((nr, nc))
        return seen[rows - 1][cols - 1]

    lo, hi = 0, max(max(row) for row in heights)
    while lo < hi:
        mid = (lo + hi) // 2
        if reachable(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Java

private static boolean effortReachable(int[][] heights, int limit) {
    int rows = heights.length, cols = heights[0].length;
    boolean[][] seen = new boolean[rows][cols];
    seen[0][0] = true;
    Deque<int[]> stack = new ArrayDeque<>();
    stack.push(new int[]{0, 0});
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};
    while (!stack.isEmpty()) {
        int[] cell = stack.pop();
        if (cell[0] == rows - 1 && cell[1] == cols - 1) return true;
        for (int d = 0; d < 4; d++) {
            int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || seen[nr][nc]) continue;
            if (Math.abs(heights[nr][nc] - heights[cell[0]][cell[1]]) > limit) continue;
            seen[nr][nc] = true;
            stack.push(new int[]{nr, nc});
        }
    }
    return seen[rows - 1][cols - 1];
}

public static int minimumEffortPath(int[][] heights) {
    int lo = 0, hi = 0;
    for (int[] row : heights) {
        for (int value : row) hi = Math.max(hi, value);
    }
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (effortReachable(heights, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

C++

static bool effortReachable(vector<vector<int>>& heights, int limit) {
    int rows = (int) heights.size(), cols = (int) heights[0].size();
    vector<vector<bool>> seen(rows, vector<bool>(cols, false));
    seen[0][0] = true;
    vector<pair<int,int>> stack;
    stack.push_back(make_pair(0, 0));
    int dr[4] = {1, -1, 0, 0};
    int dc[4] = {0, 0, 1, -1};
    while (!stack.empty()) {
        pair<int,int> cell = stack.back();
        stack.pop_back();
        if (cell.first == rows - 1 && cell.second == cols - 1) return true;
        for (int d = 0; d < 4; d++) {
            int nr = cell.first + dr[d], nc = cell.second + dc[d];
            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || seen[nr][nc]) continue;
            if (abs(heights[nr][nc] - heights[cell.first][cell.second]) > limit) continue;
            seen[nr][nc] = true;
            stack.push_back(make_pair(nr, nc));
        }
    }
    return seen[rows - 1][cols - 1];
}

int minimumEffortPath(vector<vector<int>>& heights) {
    int lo = 0, hi = 0;
    for (const auto& row : heights) {
        for (int value : row) hi = max(hi, value);
    }
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (effortReachable(heights, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

JavaScript

var minimumEffortPath = function(heights) {
    const rows = heights.length, cols = heights[0].length;
    const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    const reachable = function(limit) {
        const seen = [];
        for (let r = 0; r < rows; r++) {
            const row = [];
            for (let c = 0; c < cols; c++) row.push(false);
            seen.push(row);
        }
        seen[0][0] = true;
        const stack = [[0, 0]];
        while (stack.length > 0) {
            const cell = stack.pop();
            if (cell[0] === rows - 1 && cell[1] === cols - 1) return true;
            for (let d = 0; d < 4; d++) {
                const nr = cell[0] + dr[d], nc = cell[1] + dc[d];
                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || seen[nr][nc]) continue;
                const diff = Math.abs(heights[nr][nc] - heights[cell[0]][cell[1]]);
                if (diff > limit) continue;
                seen[nr][nc] = true;
                stack.push([nr, nc]);
            }
        }
        return seen[rows - 1][cols - 1];
    };
    let lo = 0, hi = 0;
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (heights[r][c] > hi) hi = heights[r][c];
        }
    }
    while (lo < hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (reachable(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium