115. Path with Minimum Effort
Travel between the two opposite corner cells using orthogonal moves. For each route, measure the largest absolute height difference across any one of its moves, then minimize that measure.
Do not add height differences together: route effort is the worst individual step. A route with no movement has effort zero.
Example 1
Input
[[1,2,2],[3,8,2],[5,3,5]]
Output
2
Explanation: The route 1→3→5→3→5 has jumps 2,2,2,2. Summing them would optimize a different objective.
Example 2
Input
[[MIN,MAX]]
Output
4294967295
Explanation: The only move spans the full signed-int height range.
Example 3
Input
[[7]], [], or [[],[]]
Output
0
Explanation: There is no required edge jump in each case.
Constraints
0 <= heights.length <= 1050 <= total heights cells <= 105-231 <= heights[r][c] <= 231 - 1- All rows have equal length and are non-null.
Hints
Hint 1
How does appending one edge change the largest jump so far?
Hint 2
The extension max(old,jump) never lowers a path cost.
Hint 3
Use Dijkstra with bottleneck relaxation, or binary search an allowed-jump threshold and test BFS reachability.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
A gentle detour beats a steep center
[[1,2,2],[3,8,2],[5,3,5]]
2