DSA problem
Path With Minimum Effort
You are a hiker preparing for an upcoming trail. You are given heights, a 2D array of size rows x columns, where heights[r][c] represents the height of cell (r, c). You start at the top-left cell (0, 0) and want to reach the bottom-right cell (rows-1, columns-1). You can move up, down, left, or right and you wish to minimize the effort of the path. The effort of a path is defined as the maximum absolute difference in heights between two consecutive cells of the path. Return the minimum effort required to travel from top-left to bottom-right.
This is not a sum-based shortest path — the cost of a path is its single most expensive edge, not the sum of edges. We want the path whose "bottleneck" edge is as small as possible. This kind of bottleneck shortest path can still be solved with a Dijkstra-like algorithm by replacing addition with max.
The idea is to maintain an effort[r][c] array representing the smallest known bottleneck to reach cell (r, c). Use a min-heap keyed by effort: pop the cell with the smallest effort so far, and for each neighbor compute new_effort = max(current_effort, abs(height_diff)). If that improves the neighbor's known effort, push it onto the heap.
The first time the destination is popped, the value is the answer because Dijkstra finalizes each node on its first pop. The transformation sum -> max does not break Dijkstra's correctness because max is monotonic and non-negative. The algorithm runs in O(m * n * log(m * n)) time and O(m * n) space, where m and n are the grid dimensions.
Examples
heights = [[1,2,2],[3,8,2],[5,3,5]]2heights = [[1,2,3],[3,8,4],[5,3,5]]1heights = [[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]]0Constraints
- rows == heights.length
- columns == heights[i].length
- 1 <= rows, columns <= 100
- 1 <= heights[i][j] <= 10^6
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.