Path With Minimum Effort | Leetcode 1631 | Explained

Path With Minimum Effort made easy: understand LeetCode 1631 with a Dijkstra heap, 4-way moves, and fully commented Python code for students.

Here’s the [Problem Link] to begin with.

1. What does the problem ask?

You get an m × n matrix heights, where heights[r][c] is the altitude of cell (r, c).

• You start at the top-left cell (0,0) and must reach the bottom-right cell (m-1,n-1).
• You may step up, down, left, or right (no diagonals).
• Effort of a path = the largest absolute height difference between any two consecutive cells along that path.

Return the smallest possible effort among all valid paths.

2. Tiny examples

3. Intuition & approach

3.1 Why classic shortest-path ideas fail

If we tried normal BFS (each step cost = 1) we would only count how many steps, ignoring height gaps.
If we tried Dijkstra with “edge weight = absolute height diff”, we would minimise total sum, not the maximum diff.

3.2 The trick: treat effort so far as the key

Think of each move having a cost equal to its height gap, but our goal is to minimise the worst cost seen so far on the path.

Dijkstra’s greedy rule still works if we define the key of each cell as:

effort(cell) = min possible maximum gap to reach this cell

Because the algorithm always pops the currently smallest effort cell, once we pop the bottom-right cell we are guaranteed that no smaller effort exists.

3.3 Algorithm steps

1. Distance grid effort_arr – keeps best known effort for every cell, initialised to ∞, except effort_arr[0][0] = 0.
2. Min-heap – store (current_effort, row, col). Start with (0,0,0).
3. Loop until heap is empty
   1. Pop the cell with the smallest effort so far.
   2. If it is the goal, return its effort (greedy guarantee).
   3. For each of the four neighbours inside the grid and not blocked:
      • step_gap = |height[next] − height[curr]|
      • new_effort = max(current_effort, step_gap)
      • If new_effort improves the neighbour’s value in effort_arr, update and push it into the heap.
4. If we exhaust the heap (the grid is always connected so this won’t happen), return 0.

Because each cell may improve at most once, the loop is O(m × n log(m × n)).

4. Code

import sys
import heapq
from typing import List


class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        rows = len(heights)
        cols = len(heights[0])

        # 1. distance grid: best effort seen so far for every cell
        effort_arr = [[sys.maxsize for _ in range(cols)] for _ in range(rows)]
        effort_arr[0][0] = 0

        # 2. min-heap with tuples (effort, row, col)
        priority_queue = [[0, 0, 0]]

        while priority_queue:
            eff, i, j = heapq.heappop(priority_queue)

            # 3. goal reached – current effort is already minimal
            if i == rows - 1 and j == cols - 1:
                return eff

            # 4. explore four neighbours
            for x, y in [[-1, 0], [0, -1], [1, 0], [0, 1]]:
                new_i, new_j = i + x, j + y
                # skip when out of bounds
                if new_i < 0 or new_j < 0 or new_i >= rows or new_j >= cols:
                    continue

                # effort of stepping into neighbour
                step_gap = abs(heights[new_i][new_j] - heights[i][j])
                new_eff  = max(eff, step_gap)

                # 5. relax if we found a gentler path
                if new_eff < effort_arr[new_i][new_j]:
                    effort_arr[new_i][new_j] = new_eff
                    heapq.heappush(priority_queue, [new_eff, new_i, new_j])

5. Line-by-line walkthrough

1. Rows & Cols – grid size.
2. effort_arr – imagine each cell filled with “∞ degrees of pain”; source cell has 0.
3. Heap push – (0,0,0) means no effort yet at (0,0).
4. Pop lowest effort – greedily safe because all weights are non-negative.
5. Neighbour loop – only 4 directions (problem requirement).
6. step_gap – vertical difference between the two cells.
7. new_eff – worst gap encountered on the candidate path to neighbour.
8. Relaxation – keep the gentlest path; push neighbour for future processing.
9. Early return – the first time we pop the bottom-right, we’re done.

6. Dry run on a 3 × 3 grid

1  2  2
3  8  2
5  3  5

Path taken: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) with max gap 2.

7. Complexity

8. Conclusion

• Treat effort as a distance metric whose cost of an edge is its height gap and whose path cost is the maximum edge cost so far.
• Running Dijkstra on that metric directly solves Path With Minimum Effort.
• Early-exit once the destination cell leaves the heap – the answer is already optimal.

Remember: when you see “minimise the maximum along the path”, think of Dijkstra with a custom aggregation like max() instead of +.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.