0577MediumArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindHeap (Priority Queue)MatrixDijkstra's Algorithm

Route With the Gentlest Climb

Tracked in this browser only

Write code

Trains the technique from

LeetCode 1631Path With Minimum Effort

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A survey of a hillside is stored in heights, a rectangle of cells where heights[r][c] is the ground elevation of cell r, c.

A porter begins in the corner cell at row 0, column 0. The drop-off is the opposite corner, the cell in the last row and the last column. One step of a route moves to a cell sharing a full edge with the cell being left, so up, down, left and right are all available, and a route may cross ground it has already covered.

The strain of a route is the largest single climb or drop it contains, that is the largest absolute elevation difference between two cells that the route steps between. A route that never leaves its starting cell has strain 0.

Return the smallest strain reachable by a route joining those two corner cells.

Examples

Example 1

Input: heights = [[1, 10, 6]]
Output: 9

The porter has one cell of choice and must cross from 1 to 10 and then from 10 to 6, so the route contains a climb of 9 and a drop of 4, and its strain is 9.

Example 2

Input: heights = [[4, 99, 6, 7, 9], [5, 99, 7, 91, 10], [6, 8, 8, 90, 11]]
Output: 2

The route 4, 5, 6, 8, 8, 7, 6, 7, 9, 10, 11 walks down the first column, right along the bottom row to the middle column, up that column to the top row, then right and down the last column. Its steps differ by 1, 1, 2, 0, 1, 1, 1, 2, 1 and 1, so its strain is 2.

Example 3

Input: heights = [[3, 3, 3], [3, 3, 3]]
Output: 0

Every cell records the same elevation, so any route has no climb at all.

Constraints

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^6

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def minimum_effort_path(heights: list[list[int]]) -> int:

Java

public int minimumEffortPath(int[][] heights)

The intended approach

Time O(rows * columns * log(rows * columns)) — every cell is settled once and each of its four steps costs a heap push.Space O(rows * columns) for the settled flags and the heap.

Run a shortest-path search where the label of a route is not a sum but the largest step it has taken: extending a route by one step gives the larger of the route's label and that step's climb. Because extending never lowers a label, a min-heap keyed on the label settles cells in non-decreasing order of best achievable strain, so a cell popped for the first time already holds its answer and the far corner's first pop is the result. All four orthogonal steps are offered from every settled cell, which lets a route wander sideways or backwards when that avoids a steep face.

Pythonentry point: minimum_effort_path

def minimum_effort_path(heights):
    # O(rows*cols*log(rows*cols)) time, O(rows*cols) space: a shortest-path
    # search where the cost of extending a route is the larger of the route's
    # current strain and the climb of the new step. A heap always settles the
    # cell reachable with the smallest strain, so the first time the far corner
    # is settled that strain is the best possible.
    import heapq
    rows = len(heights)
    cols = len(heights[0])
    settled = [[False] * cols for _ in range(rows)]
    heap = [(0, 0, 0)]
    while heap:
        strain, r, c = heapq.heappop(heap)
        if settled[r][c]:
            continue
        settled[r][c] = True
        if r == rows - 1 and c == cols - 1:
            return strain
        here = heights[r][c]
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr = r + dr
            nc = c + dc
            if 0 <= nr < rows and 0 <= nc < cols and not settled[nr][nc]:
                step = here - heights[nr][nc]
                if step < 0:
                    step = -step
                heapq.heappush(heap, (strain if strain > step else step, nr, nc))
    return 0

The obvious version

The answer is one of the absolute differences between neighbouring cells, or zero, so collect those values and sort them. For a fixed limit, a plain queue-based flood fill that only crosses edges within the limit says whether the far corner is reachable, and reachability only improves as the limit grows, so binary search the sorted list for the smallest workable limit.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_minimum_effort_path(heights):
    from collections import deque
    rows = len(heights)
    cols = len(heights[0])
    candidates = {0}
    for r in range(rows):
        for c in range(cols):
            if r + 1 < rows:
                candidates.add(abs(heights[r][c] - heights[r + 1][c]))
            if c + 1 < cols:
                candidates.add(abs(heights[r][c] - heights[r][c + 1]))
    options = sorted(candidates)

    def reachable(limit):
        seen = [[False] * cols for _ in range(rows)]
        seen[0][0] = True
        queue = deque([(0, 0)])
        while queue:
            r, c = queue.popleft()
            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
                        queue.append((nr, nc))
        return False

    lo = 0
    hi = len(options) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if reachable(options[mid]):
            hi = mid
        else:
            lo = mid + 1
    return options[lo]

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in