Minimum Worst Step Path

You are given a rows x columns integer grid grid, where grid[r][c] is the height at that cell.

Starting at the top-left cell (0, 0), you want to reach the bottom-right cell (rows - 1, columns - 1), moving only between cells that share an edge (up, down, left or right).

The cost of a path is the largest absolute height difference between any two consecutive cells on it, not the total, only the single worst step.

Return the smallest cost achievable over all paths.

Examples

Example 1

Input: grid = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route down the right-hand side and along the bottom has consecutive differences of at most 2. Any route through the height-8 cell has a step of at least 5.

Example 2

Input: grid = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: A route exists whose every step changes the height by at most 1.

Example 3

Input: grid = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: A route exists that only ever moves between cells of equal height, so its worst step is 0.