NeetCode #627LC-1631MediumAdvanced GraphsNC 250
← Back to All Problems#627 · #1631 · Path With Minimum Effort(最小体力消耗路径)
📌 Problem Statement & Constraints
You are given an
m x n grid of heights. A route's effort is the maximum absolute difference in heights between consecutive cells. Return the minimum effort to travel from the top-left to the bottom-right, moving in the four cardinal directions. Constraints: 1 <= m, n <= 100, 1 <= heights[i][j] <= 10^6.💡 Core Algorithmic Approaches
- The same Dijkstra variant as Swim in Rising Water: minimise the maximum edge weight along the path.
- The heap key is the effort so far, and neighbours are pushed with
max(current, |height difference|). - The first pop of the destination gives the answer.
- Alternatively, binary search the effort and check connectivity with BFS.
💻 Benchmark Python3 Implementation
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
import heapq
m, n = len(heights), len(heights[0])
h = [(0, 0, 0)] # (effort so far, r, c)
seen = {(0, 0)}
while h:
effort, r, c = heapq.heappop(h)
if r == m - 1 and c == n - 1:
return effort
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in seen:
seen.add((nr, nc))
step = abs(heights[nr][nc] - heights[r][c])
heapq.heappush(h, (max(effort, step), nr, nc))
return 0⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n log(m * n)): each cell is pushed once.
💾 Space Complexity
O(m * n) for the heap and the visited set.
⚠️ Interview Pitfalls & Follow-ups
- Summing the differences: the effort is the maximum, not the sum.
- Forgetting the absolute value: the difference can be negative.
- Marking visited when popping: workable, but marking on push is safe here because the first pop is optimal.
- Using a plain BFS: it ignores the weights.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.