Path With Minimum Effort

Standard Bar Graphs · Shortest Path Problems O(rows * columns * log(rows * columns)) · O(rows * columns)

Smoothing the Crossover Conveyor Route

A robotic picking floor connects bays of differing platform heights, and a fragile-load cart must cross from the intake corner to the dispatch corner. The jolt a cart suffers between two adjacent bays is their height difference, and a route's roughness is its single worst jolt. Route planning must minimise that worst jolt — not the number of steps.

Input: A rows x columns matrix heights where heights[r][c] is the platform height of bay (r, c).

Output: Return the minimum possible value of the maximum absolute height difference along a 4-directional route from (0,0) to (rows-1, columns-1).

Constraints

1 <= rows, columns <= 100
1 <= heights[r][c] <= 10^6

Examples

Example 1

Input: {"heights":[[1,2,2],[3,8,2],[5,3,5]]}
Output: 2
Riding 1 -> 3 -> 5 -> 3 -> 5 never jolts worse than 2, beating the direct top-row route's 3.

Example 2

Input: {"heights":[[1,2,3],[3,8,4],[5,3,5]]}
Output: 1
A staircase of neighbouring heights exists where every consecutive pair differs by at most 1.

Solve this in your browser →

Also on LeetCode ↗