Path With Minimum Effort

Given a rectangular grid of heights, move up, left, down or right from the top-left to the bottom-right cell. A route effort is the maximum absolute height…

Given a rectangular grid of heights, move up, left, down or right from the top-left to the bottom-right cell. A route effort is the maximum absolute height difference between consecutive cells. Return the minimum possible route effort. A one-cell route has effort zero.

1 <= rows, columns <= 100; 1 <= heights[r][c] <= 1000000. Visual presets are limited to 6×6.

Example 1: input heights = [[1,2,2],[3,8,2],[5,3,5]]; output 2. The left-and-bottom route follows heights 1, 3, 5, 3, 5 with maximum jump two. No threshold below two connects the start to the destination.

Example 2: input heights = [[1,2,3],[3,8,4],[5,3,5]]; output 1. The top-and-right route follows heights 1, 2, 3, 4, 5 with maximum jump one. Effort zero cannot leave the starting cell, so one is optimal.

Category: Graphs. Topic: graph. Difficulty: Hard. Patterns: graph-traversal.