1631. Path with Minimum Effort (Dijkstra + minHeap)

Edited by Charles

Medium · Python · Graph

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

This problem can be treated as a shortest path problem on a grid.

Original study notes follow, including intermediate snippets and earlier attempts.

Approach: Dijkstra + Min Heap

This problem can be treated as a shortest path problem on a grid.

Each cell (row, col) is a node, and each node can connect to at most four neighbors:

up, down, left, right

Unlike a normal graph problem, we do not need to explicitly build an adjacency list. The neighbors of each cell can be generated directly using four directions.

Graph Representation

For a grid with:

m = len(heights)
n = len(heights[0])

there are:

m × n nodes

Each cell:

(row, col)

represents one node.

Instead of building an adjacency list, define four directions:

Directions = [
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1)
]

For the current node (curRow, curCol), a neighbor can be generated by:

nextRow = curRow + rowDelta
nextCol = curCol + colDelta

Then check whether it is inside the grid:

0 <= nextRow < m and 0 <= nextCol < n

Therefore, the grid itself can be viewed as an implicit graph.

Definition of Effort

The edge weight between two adjacent cells is their absolute height difference:

abs(
    heights[nextRow][nextCol]
    - heights[curRow][curCol]
)

However, the effort of an entire path is not the sum of all edge weights.

It is the maximum height difference along the path.

For example:

Edge differences:

2 → 5 → 3

The effort of this path is:

max(2, 5, 3) = 5

not:

2 + 5 + 3 = 10

Our goal is to find a path from the top-left cell to the bottom-right cell whose maximum edge difference is as small as possible.

minEffort Matrix

Create:

minEffort = [[float('inf')] * n for _ in range(m)]
minEffort[0][0] = 0

minEffort[row][col] represents:

The minimum possible effort required to travel from (0, 0) to (row, col).

The starting point requires no effort:

minEffort[0][0] = 0

All other cells are initially unreachable, so their efforts are initialized to infinity.

Min Heap

Initialize:

minHeap = [(0, 0, 0)]

Each heap entry stores:

(effort, row, col)

For example:

(3, 1, 2)

means that the current known effort required to reach (1, 2) is 3.

Since effort is the first element of the tuple, Python's heapq always pops the state with the smallest effort first.

Skip Outdated Heap States

A cell may be pushed into the heap multiple times if a better path is discovered later.

Therefore:

if curEffort > minEffort[curRow][curCol]:
    continue

If:

curEffort > minEffort[curRow][curCol]

then the heap entry is outdated because a better path to the same cell has already been found.

We can safely skip it.

This is the same lazy deletion idea used in standard Dijkstra.

Relaxation

Suppose we are currently at:

(curRow, curCol)

and move to:

(nextRow, nextCol)

First calculate the effort of this edge:

edgeEffort = abs(
    heights[nextRow][nextCol]
    - heights[curRow][curCol]
)

Since the effort of a path is the maximum edge difference along that path, the new path effort is:

newEffort = max(edgeEffort, curEffort)

Then perform relaxation:

if newEffort < minEffort[nextRow][nextCol]:
    minEffort[nextRow][nextCol] = newEffort
    heapq.heappush(
        minHeap,
        (newEffort, nextRow, nextCol)
    )

If the new path gives a smaller effort, update minEffort and push the new state into the heap.

Why Dijkstra Still Works

Standard Dijkstra minimizes:

sum of edge weights

For example:

newDist = curDist + weight

In this problem, we minimize:

maximum edge weight along the path

Therefore, the relaxation formula changes to:

newEffort = max(curEffort, edgeEffort)

The rest of the Dijkstra framework remains the same.

Early Termination

When the bottom-right cell is popped from the min heap:

if curRow == m - 1 and curCol == n - 1:
    break

its minimum effort has already been determined.

This is because Dijkstra always processes the state with the smallest current effort first.

Therefore, we do not need to continue exploring the remaining nodes.

Finally:

return minEffort[-1][-1]

Comparison with LeetCode 743

	743 Network Delay Time	1631 Minimum Effort Path
Graph	Explicit graph	Grid / implicit graph
Node	node	(row, col)
Neighbors	Adjacency list	4 directions
Distance structure	1D array	2D matrix
Heap	(dist, node)	(effort, row, col)
Edge weight	Given w	Height difference
Path cost	Sum of weights	Maximum edge weight
Relaxation	curDist + weight	max(curEffort, edgeEffort)

The main difference is the definition of the path cost.

LeetCode 743

newDist = curDist + weight

LeetCode 1631

newEffort = max(
    curEffort,
    abs(height1 - height2)
)

The overall Dijkstra structure remains unchanged.

Complexity

Let:

V = m × n

Each cell has at most 4 edges, so:

E = O(m × n)

Time Complexity

O(m × n × log(m × n))

Each node/edge may cause a heap operation, and each heap operation costs O(log(m × n)).

Space Complexity

O(m × n)

Used by:

• minEffort
• minHeap

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	August 28, 2026

Python solution

import heapq

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m, n = len(heights), len(heights[0])
        Directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        minEffort = [[float('inf')] * n for _ in range(m)]
        minEffort[0][0] = 0

        minHeap = [(0, 0, 0)]

        while minHeap:
            curEffort, curRow, curCol = heapq.heappop(minHeap)

            if curEffort > minEffort[curRow][curCol]:
                continue

            if curRow == m - 1 and curCol == n - 1:
                break

            for rowDelta, colDelta in Directions:
                nextRow = curRow + rowDelta
                nextCol = curCol + colDelta

                if 0 <= nextRow < m and 0 <= nextCol < n:
                    newEffort = max(
                        abs(
                            heights[nextRow][nextCol]
                            - heights[curRow][curCol]
                        ),
                        curEffort
                    )

                    if newEffort < minEffort[nextRow][nextCol]:
                        minEffort[nextRow][nextCol] = newEffort
                        heapq.heappush(
                            minHeap,
                            (newEffort, nextRow, nextCol)
                        )

        return minEffort[-1][-1]

---

Back to Day 52 Graph X · All Algorithm notes