Gentlest Hiking Route

MediumAdvanced Graphs

Problem

A trail map is a grid heights where heights[r][c] is the altitude of a square. A hiker starts at the top-left square and wants to reach the bottom-right square, moving one square up, down, left or right at a time.

The strain of a route is the largest absolute altitude difference between two consecutive squares on it. Return the minimum possible strain.

Example 1

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

Route 1 → 2 → 3 → 4 → 4 never changes altitude by more than 1.

Example 2

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

Example 3

Input:
heights = [[7]]
Output:
0

The hiker is already at the goal.

Constraints

  • 1 ≤ rows, cols ≤ 100
  • 1 ≤ heights[r][c] ≤ 10^6

Hint

Show the first hint

The cost of a route is not a sum but a maximum. Does Dijkstra still apply?

Walkthrough

How to approach it

01Clarify before coding

  • Can the hiker move diagonally? No, only the four orthogonal directions.
  • Is the strain a sum or a maximum? The maximum single step on the route.
  • Can squares be revisited? Yes, but it never helps.

02Brute force

Try every simple path with DFS and track the largest step on each.

Cost: Exponential in the number of squares; a 100 × 100 grid makes it hopeless.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.