Asked at

Path With Minimum Effort

Hard
VerifiedDijkstraHeapMatrixBinary Search~35 min

You’re given a grid heights where heights[r][c] is the elevation of a cell. Start at the top-left and reach the bottom-right, moving in four directions. A route’s effort is the maximum absolute height difference between consecutive cells along it.

Return the minimum effort over all routes. The input is the grid number[][] directly.

Examples

in[[1,2,2],[3,8,2],[5,3,5]]
out2

Route 1→3→5→3→5 keeps every step's height jump ≤ 2.

in[[1,2,3],[3,8,4],[5,3,5]]
out1

A path exists where no adjacent height differs by more than 1.

Constraints

  • 1 ≤ rows, cols ≤ 100
  • 1 ≤ heights[r][c] ≤ 10⁶
  • Move up, down, left, or right.

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.