Path With Minimum Effort

The key idea

The cost of a route is its single worst step, not the sum of its steps. So you do not minimize total distance — you minimize the largest absolute height difference along the way. That bottleneck framing turns the problem into a reachability question: for a given effort limit, can you reach the end using only steps no bigger than that limit?

Problem

You are given a grid heights of size rows x columns, where heights[row][col] is the height of cell (row, col). You start at the top-left cell (0, 0) and you want to travel to the bottom-right cell (rows-1, columns-1). You can move up, down, left, or right, and you cannot leave the grid.

A route's effort is the maximum absolute difference in heights between two consecutive cells along the route. Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Constraints

rows == heights.length
columns == heights[0].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^6

Examples

Input: heights = [[1,2,2],[3,8,2],[5,3,5]] Output: 2

Input: heights = [[1,2,3],[3,8,4],[5,3,5]] Output: 1

Input: heights = [[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]] Output: 0

Complexity

Time: O(R*C*log(maxH)) Space: O(R*C)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →