Path With Minimum Effort
You are planning a hike across a map given as a rows × cols grid heights, where heights[r][c] is the height of cell (r, c). You start at the top-left cell (0, 0) and want to reach the bottom-right cell (rows - 1, cols - 1). From any cell you may move up, down, left or right.
The effort of a route is the largest absolute height difference between two consecutive cells on it. A long route with gentle steps can beat a short route with one steep step.
Return the minimum effort of any route from the start to the finish.
Constraints
1 <= rows, cols <= 1001 <= heights[r][c] <= 10^6
Examples
Example 1
Input: heights = [[1,2,9],[5,3,8],[4,6,2]] Output: 4
Going 1 → 2 → 3 → 6 → 2 has steps of 1, 1, 3 and 4, so its effort is 4. Every route has to make a step of at least 4 somewhere.
Example 2
Input: heights = [[5]] Output: 0
You start on the destination, so no step is needed: 0.
Example 3
Input: heights = [[1,100,1],[1,100,1],[1,1,1]] Output: 0
Go down the left column and along the bottom row: every cell is 1, so the effort is 0. Crossing the 100s would cost 99.
JavaScript you'll use: Heaps and priority queues Graphs and grids in JavaScript Numbers, Math and integer tricks
/**
* @param {number[][]} heights
* @return {number}
*/
function minimumEffortPath(heights) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.