Hiking Trail - Find Optimal Path Under Elevation and Distance Constraints

Question

## Round 1 - Coding

## Problem

You are given a grid representing a hiking map. Each cell has an elevation value. You start at the top-left corner and want to reach the bottom-right corner. You can move up, down, left, or right. Find the path that minimizes the maximum elevation change between any two consecutive steps.

```python
def hiking_trail(grid: list[list[int]]) -> int:
    # grid[i][j] = elevation at cell (i, j)
    # Return the minimum possible value of:
    #   max |elevation[step_k] - elevation[step_k+1]| over all steps in path
    ...
```

```
Example:
grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
# Path: (0,0)->1, (0,1)->2, (0,2)->3, (1,2)->6, (2,2)->9
# Max step diff: max(1,1,3,3) = 3
# Optimal path minimizes this. Answer:
hiking_trail(grid) -> 1  # via zigzag path with all diffs = 1
```

## Follow-ups

1. Is BFS or Dijkstra more appropriate here? Why?
2. Can binary search on the answer help? How would you combine it with BFS?
3. How does the problem change if you want to minimize total elevation gain (sum) rather than max step?
4. How would you handle a grid with impassable cells?

Hiking Trail - Find Optimal Path Under Elevation and Distance Constraints

Question Details

Full Details

Topics

More from Pinterest