MediumPro challengePythonJavaScriptTypeScript
Graph — Path With Minimum Effort
Data StructuresGraphsDijkstraMatrix
solve(heights) — you start at the top-left cell of a grid and want to reach the
bottom-right cell, moving up, down, left or right. The effort of a path is the
largest absolute height difference between two consecutive cells on it. Return the
minimum effort over all paths.
This is Dijkstra with a twist: the "distance" of a path is the maximum edge on
it instead of the sum, and it still works because extending a path can never lower
it. A MinHeap ordered by item[0] is provided for JavaScript and TypeScript;
Python has heapq.
Examples
solve([[1,2,2],[3,8,2],[5,3,5]]) → 2
solve([[1,2,3],[3,8,4],[5,3,5]]) → 1
solve([[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]]) → 0
solve([[1]]) → 0Sample tests
Test #1Classic example
Input: [[[1,2,2],[3,8,2],[5,3,5]]]
Output: 2
Test #2Smoother route exists
Input: [[[1,2,3],[3,8,4],[5,3,5]]]
Output: 1
Test #3Single cell
Input: [[[1]]]
Output: 0