Path With Minimum Effort
Medium · Advanced Graphs · Array · Binary Search · Depth-First Search · Breadth-First Search · Union Find · Heap (Priority Queue) · Matrix
Problem
You are hiking across a grid heights of rows x cols cells, where heights[r][c] is the height of cell (r, c). You start at the top-left cell (0, 0) and must reach the bottom-right cell (rows - 1, cols - 1), moving up, down, left or right one cell at a time.
The effort of a route is the largest absolute height difference between two consecutive cells on it. Return the smallest effort of any route from the start to the destination.
Examples
Input: heights = [[1,8,2],[3,4,9],[5,6,3]] Output: 3
The route 1 → 3 → 5 → 6 → 3 never changes height by more than 3 in one step.
Input: heights = [[4,4,4],[4,4,4]] Output: 0
Every step is level, so no effort is needed.
Input: heights = [[1,9,1,1,1],[1,9,1,9,1],[1,1,1,9,1]] Output: 0
Down the first column, up the middle one and down the last one: every cell on that route has height 1, so the effort is 0.
Constraints
- rows == len(heights), cols == len(heights[i])
- 1 <= rows, cols <= 100
- 1 <= heights[r][c] <= 10^6
Approaches
- Try every possible effort, smallest first — time O(D · R · C), space O(R · C)
Follow-up
Two other good solutions exist. Binary search on the limit with a flood fill per guess is O(rows · cols · log 10^6). Or sort every edge between neighbors by its height difference and join cells with union-find in that order: the first edge that connects the two corners is the answer (a minimum spanning tree idea), O(E log E).
Related problems
Start free on Cariara · Coding problems · System design studio
