Path with Minimum Effort

MEDIUM✓ CHIP-TIMEDLC #1631 — FULL STATEMENT ↗

The drill: Walk a grid from the top-left cell to the bottom-right one, where each step costs the absolute height difference to the next cell. Minimize the worst single step on the route — not the total climbed.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A grid of elevation values arrives, and the walk goes from the top-left cell to the bottom-right one, moving only up, down, left, or right one cell at a time.

Each step between two cells costs the absolute difference in their elevations. A route's overall cost isn't the sum of those step costs — it's just the single largest step anywhere along the way.

The task is to pick a route, among all the ones that reach the bottom-right corner, whose worst single step is as small as possible. Multiple routes can tie on that worst-step value.

EX 01

heights = [[5]]

→ 0

SINGLE CELL, NO MOVEMENT NEEDED

EX 02

heights = [[1, 10]]

→ 9

TWO CELLS, ONE EDGE

EX 03

heights = [[3], [8]]

→ 5

VERTICAL PAIR

grid can span roughly a couple hundred rows and columns
elevations are non-negative integers, can repeat
movement is only the four orthogonal directions, no diagonals
route cost is the maximum single-step difference, not a running sum
answer is that minimized maximum step value

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A route's cost isn't a sum of its steps — it's just the single worst step along the way. That changes what "shortest" means before any algorithm gets involved.

HINT 2 THE STRUCTURE

This is still shortest-path, but the edge weight of a step folds into the running cost with max, not addition. Anything that generalizes Dijkstra to a different combine operator will work.

HINT 3 ONE STEP FROM THE ANSWER

Run Dijkstra from the start cell. Relax with newEffort = max(currentEffort, heightDiff) instead of currentEffort + heightDiff, and stop the moment the goal cell is popped off the heap.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE GENTLEST CLIMBPATTERN · DIJKSTRA, MAX NOT SUMheights = [[1,2,3],[3,8,4],[5,3,5]]

STEP 1

Start the climb at (0,0), effort 0. A min-heap always pops the cheapest reachable cell next — Dijkstra, but relaxation takes the MAX step instead of a sum.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/path-with-minimum-effort.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        rows, cols = len(heights), len(heights[0])
        dist = [[float('inf')] * cols for _ in range(rows)]
        dist[0][0] = 0
        pq = [(0, 0, 0)]
        while pq:
            d, r, c = heapq.heappop(pq)
            if d > dist[r][c]:
                continue
            if r == rows - 1 and c == cols - 1:
                return d
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    nd = max(d, abs(heights[nr][nc] - heights[r][c]))
                    if nd < dist[nr][nc]:
                        dist[nr][nc] = nd
                        heapq.heappush(pq, (nd, nr, nc))
        return 0

TIME O(ROWS·COLS·LOG(ROWS·COLS))SPACE O(ROWS·COLS)PYTHON · RACE PACE · 20 LN

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        rows, cols = len(heights), len(heights[0])
        best = [float('inf')]
        visited = [[False] * cols for _ in range(rows)]

        def dfs(r, c, cur_effort):
            if cur_effort >= best[0]:
                return
            if r == rows - 1 and c == cols - 1:
                best[0] = cur_effort
                return
            visited[r][c] = True
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]:
                    ne = max(cur_effort, abs(heights[nr][nc] - heights[r][c]))
                    dfs(nr, nc, ne)
            visited[r][c] = False

        dfs(0, 0, 0)
        return best[0] if best[0] != float('inf') else 0

TIME O(4^(ROWS·COLS))SPACE O(ROWS·COLS)PYTHON · TRAINING PACE · 22 LN

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length, cols = heights[0].length;
        int[][] dist = new int[rows][cols];
        for (int[] row : dist) java.util.Arrays.fill(row, Integer.MAX_VALUE);
        dist[0][0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[] { 0, 0, 0 });
        int[][] dirs = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], r = cur[1], c = cur[2];
            if (d > dist[r][c]) continue;
            if (r == rows - 1 && c == cols - 1) return d;
            for (int[] dir : dirs) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                    int nd = Math.max(d, Math.abs(heights[nr][nc] - heights[r][c]));
                    if (nd < dist[nr][nc]) {
                        dist[nr][nc] = nd;
                        pq.offer(new int[] { nd, nr, nc });
                    }
                }
            }
        }
        return 0;
    }
}

TIME O(ROWS·COLS·LOG(ROWS·COLS))SPACE O(ROWS·COLS)JAVA · RACE PACE · 28 LN

class Solution {
    private int best;

    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length, cols = heights[0].length;
        best = Integer.MAX_VALUE;
        boolean[][] visited = new boolean[rows][cols];
        dfs(heights, 0, 0, 0, visited);
        return best == Integer.MAX_VALUE ? 0 : best;
    }

    private void dfs(int[][] h, int r, int c, int effort, boolean[][] visited) {
        if (effort >= best) return;
        int rows = h.length, cols = h[0].length;
        if (r == rows - 1 && c == cols - 1) {
            best = effort;
            return;
        }
        visited[r][c] = true;
        int[][] dirs = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]) {
                int ne = Math.max(effort, Math.abs(h[nr][nc] - h[r][c]));
                dfs(h, nr, nc, ne, visited);
            }
        }
        visited[r][c] = false;
    }
}

TIME O(4^(ROWS·COLS))SPACE O(ROWS·COLS)JAVA · TRAINING PACE · 30 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED