The problem
Hike from the top-left to the bottom-right of a heights grid. A route’s effort is the maximum absolute height difference between consecutive cells. Minimize that effort.
Stuck? Reveal hints one at a time
How to approach it
- 1Treat each cell as a node; edge weight between neighbors = |height difference|.
- 2Run Dijkstra where the distance to a node is the minimal possible "maximum edge" along any path to it.
- 3Relax: candidate = max(effort[u], edgeWeight); update if smaller than effort[v].
- 4First time the bottom-right cell is popped, its effort is the answer.
Key insight
Dijkstra needs only that the path cost never decreases as you extend a path — max() satisfies that just like +, so the greedy proof survives.
The solution
Watch out for
- Summing differences instead of taking the max answers a different (wrong) question.
- Returning only when the target is POPPED (not merely pushed) is what guarantees minimality.