Path with Minimum Effort

Path with Minimum Effort medium

Description

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows × columns, where heights[row][col] represents the height of cell (row, col).

You start at the top-left cell (0, 0) and your goal is to travel to the bottom-right cell (rows-1, columns-1). You can move 4-directionally. A route’s effort is the maximum absolute difference in heights between two consecutive cells along the route.

Return the minimum effort required to travel from top-left to bottom-right.

Examples

> Case 1:
    heights = [[1,2,2],[3,8,2],[5,3,5]]
    Output: 2
    # Path 1 → 2 → 2 → 2 → 5 has consecutive differences {1, 0, 0, 3} → max = 3
    # Path 1 → 3 → 5 → 3 → 5 has differences {2, 2, 2, 2} → max = 2
 
> Case 2:
    heights = [[1,2,3],[3,8,4],[5,3,5]]
    Output: 1
 
> Case 3:
    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

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

State design

Key insight: the cost of a path is the max edge weight along it, not the sum. So when we extend the path from u to v through edge weight w:

effort_through_u_to_v = max(effort_so_far_to_u, w)

That’s still monotone in non-negative weights — extending a path can only increase the effort (or keep it the same), never decrease it. Dijkstra’s correctness argument carries through verbatim with max in place of +.

So: Dijkstra, but replace dist[u] + w < dist[v] with max(dist[u], w) < dist[v]. Done.

Code

Analysis

Time: O(m · n · log(m · n)) — Dijkstra on m · n vertices, 4 neighbors each.
Space: O(m · n).

Alternative — binary search + BFS

There’s a clean second approach: binary search the answer.

Can I reach (m-1, n-1) using only edges with absolute height difference ≤ E?

For a fixed E, that’s a yes/no BFS / DFS question — treat any edge with difference > E as blocked, see if the target is reachable. Binary search E from 0 to max(heights). Total: O(m · n · log(maxHeight)).

Both approaches AC the problem; Dijkstra is the cleaner one for this exact pattern, and easier to remember in general because it slots into the standard template.

“Replace sum with max” generalizes broadly. Any time the “cost” of a path is determined by the worst edge — bottleneck capacity, max temperature, slowest segment — Dijkstra-with-max is the move. Same skeleton, one operator swap.

Same skin

Swim in Rising Water — same minimax shape, water level instead of height delta.
Path With Maximum Minimum Value — maximin (max the smallest edge).
Minimum Cost Path Through Grid — sum-based grid Dijkstra, same skeleton.

Cheapest Flights Within K Stops Find City with Smallest Neighbors