Path With Minimum Effort

Medium

You are given a grid heights of size rows x columns. You start at the top-left cell and want to reach the bottom-right cell, moving up, down, left, or right.

The effort of a route is the maximum absolute height difference between two consecutive cells along it.

Return the minimum effort required to travel from the top-left to the bottom-right cell.

Example 1

Input:  heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route 1 -> 2 -> 2 -> 2 -> 5 has a maximum difference of 2, better than going through 8.

Example 2

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

Constraints

• rows == heights.length
• columns == heights[i].length
• 1 <= rows, columns <= 100
• 1 <= heights[i][j] <= 10^6