Rock Climbing: Find the Minimum Effort Path Up a Climbing Wall Represented as a Height Grid

Question

## Problem

You have an `m x n` grid where each cell is a rock height. You start at `(0,0)` and must reach `(m-1,n-1)`. The effort of a path is the maximum absolute height difference between adjacent steps. Find the minimum possible effort.

```python
def min_effort(heights: list[list[int]]) -> int:
    pass
```

**Example:**
```
heights = [
  [1, 2, 2],
  [3, 8, 2],
  [5, 3, 5],
]
Path: (0,0)->(0,1)->(0,2)->(1,2)->(2,2): max diff = max(1,0,6,3) = 6
Better: (0,0)->(1,0)->(2,0)->(2,1)->(2,2): max diff = max(2,2,2,2) = 2
output -> 2
```

## Approach

Dijkstra treating effort as the priority (minimize the maximum edge weight to reach each cell). Or binary search on effort + BFS feasibility check. O(m*n log(m*n)).

## Follow-ups
1. This is the "minimax path" variant. How does it differ from the classic shortest-path problem?
2. Binary search + BFS is an alternative. What is its complexity and when would you prefer it?
3. You can also descend (negative height difference). Does the algorithm change?
4. Add rest ledges that reset your accumulated effort -- how would you model that in the graph?

Rock Climbing: Find the Minimum Effort Path Up a Climbing Wall Represented as a Height Grid

Question Details

Full Details

Topics

More from Square/Block