Graphs
Path With Minimum Effort
DESCRIPTION (inspired by Leetcode.com)
A hiking app needs to find the easiest route across terrain. Given a 2D grid where each cell represents the elevation at that point, find the path from the top-left corner to the bottom-right corner that minimizes the "effort".
The effort of moving between two adjacent cells is the absolute difference in their elevations. The effort of a path is the maximum single-step effort along that path.
You can move up, down, left, or right from any cell. Return the minimum effort required.
Example 1:
Input:
heights = [[1,10,2], [2,3,3], [3,2,1]]
Output:
1
Explanation: The cliff (10) has a huge elevation difference. Going around via 1→2→3→2→1 avoids it entirely, with each step having effort at most 1.
Example 2:
Input:
heights = [[4,3,2], [2,5,3], [3,2,1]]
Output:
2
Explanation: The center peak (5) would require effort 2 to cross. Going around the top: 4→3→2→3→1 keeps maximum effort at 2.