You are hiking on a grid heights of size rows x cols and start at the top-left cell, wanting to reach the bottom-right cell. You can move up, down, left or right. The effort of a route is the largest absolute height difference between two consecutive cells on it. Return the minimum effort needed to reach the destination.
- 1 <= rows, cols <= 100
- 1 <= heights[i][j] <= 10^6
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying all routes with DFS is exponential. One fix is to binary search the answer and BFS with "only steps up to mid allowed", which is O(R*C log H). Even neater is a modified Dijkstra: let effort[cell] be the best possible maximum step to reach it. Extending a route never makes its maximum smaller, so the same greedy argument as normal Dijkstra holds: the first time we pop a cell from the min-heap, its effort is final. When we pop the destination we are done.
Algorithm
- Set
effortof every cell to infinity, except(0, 0)which is 0, and push(0, 0, 0)into a min-heap. - Pop the cell with the smallest effort. If it is the bottom-right cell, return its effort.
- Skip it if the popped effort is larger than the stored one (a stale entry).
- For each of the 4 neighbours compute
max(e, abs(height difference)); if it beats the neighbour value, update it and push.
O(R * C * log(R * C))Space: O(R * C)class Solution: def minimumEffortPath(self, heights: List[List[int]]) -> int: R, C = len(heights), len(heights[0]) effort = [[float('inf')] * C for _ in range(R)] effort[0][0] = 0 heap = [(0, 0, 0)] # (effort, row, col) while heap: e, r, c = heapq.heappop(heap) if r == R - 1 and c == C - 1: return e if e > effort[r][c]: continue # stale entry for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)): if 0 <= nr < R and 0 <= nc < C: ne = max(e, abs(heights[nr][nc] - heights[r][c])) if ne < effort[nr][nc]: effort[nr][nc] = ne heapq.heappush(heap, (ne, nr, nc)) return 0