Hack University
635/670

635. Path With Minimum Effort

Medium

A hiker starts at the top-left cell of a grid and wants to reach the bottom-right cell. heights is a rows x cols matrix where heights[r][c] is the elevation of cell (r, c). From any cell the hiker may step up, down, left, or right.

The effort of a route is the largest absolute elevation difference between any two consecutive cells on it — one brutal step ruins the whole hike, no matter how gentle the rest is. Return the smallest possible effort over all routes from (0, 0) to (rows-1, cols-1).

Your function receives the matrix of elevations and returns one integer, the minimum achievable effort. Note the objective: you are minimizing the maximum step, not the sum of steps — that difference is the whole problem.

Example 1 — the route that minimizes the worst stepThe gold route hugs the left edge and the bottom row: 1 → 3 → 5 → 3 → 5. Its steps differ by 2, 2, 2, 2, so the effort is 2. The gray route across the top looks gentle until the final drop of |2 − 5| = 3.
122382535gold route steps:|1−3| |3−5| |5−3| |3−5|effort = max(2,2,2,2) = 2gray route steps:1, 0, 0, then |2−5| = 3effort = 3 — one bad stepstart (0,0)goal (2,2)

Example 1:

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

Output: 2

Explanation: The route 1 → 3 → 5 → 3 → 5 down the left edge and along the bottom has consecutive differences 2, 2, 2, 2, so its effort is 2. The route across the top, 1 → 2 → 2 → 2 → 5, ends with a jump of 3 — worse.

Example 2:

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

Output: 1

Explanation: Going 1 → 2 → 3 → 4 → 5 along the top edge and down the right side keeps every step at exactly 1.

Constraints:

  • rows == heights.length, cols == heights[r].length
  • 1 ≤ rows, cols ≤ 100
  • 1 ≤ heights[r][c] ≤ 10⁶

Hints:

This is a shortest-path problem with an unusual cost: a path's cost is the MAXIMUM of its edge weights (|height difference|), not their sum. Standard BFS won't do; think about which classic tools still apply.

Binary search the answer: a limit E is feasible if you can reach the goal using only steps of difference <= E. Feasibility is one BFS/DFS over the cells. E is monotone — if E works, every larger limit works — so binary search over [0, max difference] pins the smallest feasible E.

Even better: run Dijkstra where the distance to a cell is the minimal possible effort to get there, relaxing with effort = max(effort[current], |height jump|) instead of a sum. The first time the goal pops off the min-heap, that value is the answer.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

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

Expected output: 2