The Gentlest Climb

Medium

A hiking map is given as a grid terrain, where terrain[r][c] is the height of the cell in row r and column c. A hiker starts in the top-left corner and wants to reach the bottom-right one. Each step moves to an adjacent cell up, down, left or right. The steepness of a step is the absolute difference between the two heights. A route is only as hard as its steepest step. Return the smallest possible difficulty of a route from start to finish.

Example 1

terrain=[[1, 4, 9], [2, 3, 8], [6, 4, 5]] → 1

The route 1 → 2 → 3 → 4 → 5 never changes height by more than 1 in a single step.

Example 2

terrain=[[5, 1], [9, 6]] → 4

Going through 1, the steepest step is 5 (from 1 to 6); going through 9, it is 4 (from 5 to 9). The second route wins.

Example 3

terrain=[[7]] → 0

The start is already the finish, so no steps are needed.

Constraints

1 ≤ number of rows, number of columns ≤ 100
All rows have the same length
1 ≤ terrain[r][c] ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Union Find Array Binary Search Matrix Heap (Priority Queue)

Similar problems

Route With the Highest Bottleneck Medium Crossing at High Tide Hard Steer Clear of the Sentries Medium Last Dry Crossing Day Hard Drain the Landlocked Ponds Medium

Input

terrain=[[1, 4, 9], [2, 3, 8], [6, 4, 5]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 71 tests on the server, hidden ones included.