Shortest Path with Minimum Effort

You are given an R × C grid heights where heights[r][c] is the height of a cell. Starting at the top-left (0,0) and moving 4-directionally to the bottom-right (R-1, C-1), a route's effort is the maximum absolute height difference between two consecutive cells on it. Return the minimum effort over all routes.

Hints

· Stuck? Reveal one nudge at a time.

A route's cost is its single worst step (the max height difference), not a sum.

reachable(t) is monotonic in t — binary-search the smallest feasible effort.

Or run Dijkstra, relaxing with max(current effort, |height diff|) instead of a sum.

Common doubts

If a route exists with every step ≤ t, one also exists for any t' > t, so feasibility is monotonic and binary search applies.

Instead of dist[u] + w, relax with max(effort[u], |Δheight|); the greedy 'settle the smallest' logic still holds since the running max is non-decreasing.

Yes — add edges in increasing difference and stop when start and end connect; the last edge's difference is the answer.

Interview follow-ups

· What an interviewer asks next.

Add the four diagonal neighbours; the algorithm is unchanged.

It's the minimax (bottleneck) shortest path, solvable by Dijkstra-with-max, binary search, or a minimum spanning tree.

Fun facts

LeetCode 1631 — the classic 'minimize the maximum edge' path problem.
The bottleneck path is an edge of the minimum spanning tree between the two cells.

Asked at

AmazonGoogleMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
A route along the right/bottom keeps every step ≤ 2; the 8 is avoided.

Example 2

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
A route exists whose largest step is 1.

Constraints

- 1 <= R, C <= 100 - 1 <= heights[r][c] <= 10^6

The cost of a route isn't a sum but a max — the single worst step. You want the route whose worst step is as small as possible (a minimax path). Two approaches:

Binary search on the answer. Guess an effort limit t; a plain BFS/DFS using only steps with height difference ≤ t tells you whether the end is reachable under that limit. reachable(t) is monotonic (more budget never hurts), so binary-search the smallest feasible t. O(R·C · log(maxHeight)).

Dijkstra with a max-relaxation. Treat cells as nodes; the "distance" to a cell is the minimum possible effort to reach it. Relax with a running maximum instead of a sum: eff[nbr] = min(eff[nbr], max(eff[cur], |Δheight|)). A min-heap settles the cell with the smallest effort first, and the answer is the effort at the destination. O(R·C · log(R·C)).

Prerequisites

Before you start

· Concepts used directly in the solution.

Minimax path. minimise the largest edge, not the sum.

Monotonic feasibility. reachable(t) is monotonic in t → binary search.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Is the cost a sum or a max?”

The max height difference along the route.

“Movement?”

4-directional.

The ideal opening — say it like this

The route cost is its worst step, so I run Dijkstra but relax with a running max instead of a sum.

Alternatively I binary-search the effort limit and BFS-check reachability under it.

Understand the problem

Worked example — heights = [[1,2,2],[3,8,2],[5,3,5]]

route 1→2→2→2→5 keeps steps ≤ 2; the 8 forces bigger jumps elsewhere
minimum effort = 2

Key observations

1Aha

Cost is a max, not a sum

Minimise the worst step (minimax path).

2Aha

Feasibility is monotonic

More effort budget only helps → binary search.

3Aha

Dijkstra with running max

Relax by max(current effort, |Δ|).

Brute force vs optimal

	Binary search + BFS	Dijkstra (max relax)
Idea	guess a limit, BFS-check reachability	settle cells by minimum effort
Time	O(R·C · log maxH)	O(R·C · log(R·C))
Cost model	threshold on steps	running max

Both return the same minimum effort. Full code is in the Approaches selector below.

Summary

Key takeaway

The route cost is its worst step. Dijkstra with a running-max relaxation settles the minimum effort to each cell; or binary-search the effort limit and BFS-check reachability. O(R·C·log …).

dijkstra: eff[nbr] = min(eff[nbr], max(eff[cur], |Δ|)); heap by effort