⚡Flashcard Drill➔
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

  1. The same Dijkstra variant as Swim in Rising Water: minimise the maximum edge weight along the path.
  2. The heap key is the effort so far, and neighbours are pushed with max(current, |height difference|).
  3. The first pop of the destination gives the answer.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems