LeetCode 1631 - Path With Minimum Effort

The problem gives us a grid called heights, where each cell contains an integer representing elevation. We start at the top-left corner (0, 0) and want to reach the bottom-right corner (rows - 1, columns - 1).

leetcodemediumarraybinary-searchdepth-first-searchbreadth-first-searchunion-findheap-(priority-queue)matrix

LeetCode Problem 1631

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Depth-First Search, Breadth-First Search, Union-Find, Heap (Priority Queue), Matrix

Solution

Problem Understanding

The problem gives us a grid called heights, where each cell contains an integer representing elevation. We start at the top-left corner (0, 0) and want to reach the bottom-right corner (rows - 1, columns - 1).

At each step, we may move in one of four directions:

  • Up
  • Down
  • Left
  • Right

The important detail is how the cost of a path is defined.

Normally, shortest path problems use the sum of edge weights. This problem is different. The effort of a path is defined as:

The maximum absolute height difference between any two consecutive cells along the path.

For example, if a path moves through height differences [1, 2, 5, 3], then the effort of the path is 5, because that is the largest jump encountered anywhere along the route.

Our goal is to minimize this maximum jump.

The input constraints are important:

  • rows, columns <= 100
  • Maximum number of cells is 100 * 100 = 10,000

This is large enough that brute-force enumeration of all paths is impossible, because the number of possible paths grows exponentially.

However, the graph size is still manageable for algorithms such as:

  • Dijkstra's algorithm
  • Binary search with BFS/DFS
  • Union-Find

The grid guarantees:

  • At least one cell exists
  • Heights are positive integers
  • The destination is always reachable because movement is unrestricted inside the grid

Several edge cases are important:

  • A single-cell grid, where no movement is needed, so effort is 0
  • A grid where all heights are identical, producing effort 0
  • A grid with one unavoidable large jump
  • Multiple possible paths where the shortest path by distance is not the minimum-effort path

The key challenge is recognizing that minimizing the maximum edge cost requires a different strategy than minimizing total distance.

Approaches

Brute Force Approach

A brute-force solution would explore every possible path from the top-left corner to the bottom-right corner.

For each path:

  1. Compute the absolute difference between consecutive cells
  2. Track the maximum difference encountered
  3. Record the minimum such value across all possible paths

This approach is correct because it explicitly checks every valid route.

However, it is computationally infeasible.

In a grid, the number of possible paths grows exponentially with the number of cells. Even for moderately sized grids, the total number of routes becomes enormous. Since the grid can contain up to 10,000 cells, exhaustive search is completely impractical.

A naive DFS with backtracking would time out.

Optimal Approach, Dijkstra's Algorithm

The key insight is that this problem can be modeled as a graph problem.

Each cell is a node.

Each move between adjacent cells is an edge with weight:

$$|heights[r1][c1] - heights[r2][c2]|$$

The challenge is that the path cost is not the sum of edge weights. Instead, the path cost is the maximum edge weight along the path.

Fortunately, Dijkstra's algorithm still works with a small modification.

Normally, Dijkstra relaxes edges using:

$$newDistance = currentDistance + edgeWeight$$

Here, we instead define:

$$newEffort = \max(currentEffort, edgeWeight)$$

This works because once we reach a node with the minimum possible effort, no future path can improve it. The monotonic property required by Dijkstra still holds.

We use a min-heap to always process the cell with the currently smallest known effort.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force DFS Exponential O(rows × cols) Explores all possible paths
Dijkstra with Min-Heap O(rows × cols × log(rows × cols)) O(rows × cols) Efficient shortest-path style solution

Algorithm Walkthrough

Optimal Algorithm Using Dijkstra's Algorithm

  1. Treat every grid cell as a graph node.

Each cell can connect to up to four neighboring cells. The edge weight between two adjacent cells is the absolute difference in heights. 2. Create a dist matrix.

dist[r][c] stores the minimum effort required to reach cell (r, c) from the start.

Initialize every value to infinity except:

dist[0][0] = 0
  1. Create a min-heap.

Each heap entry stores:

(current_effort, row, col)

Start by inserting:

(0, 0, 0)
  1. Repeatedly pop the smallest effort cell from the heap.

This guarantees we always process the currently best-known state first. 5. If the popped cell is the destination, return its effort immediately.

Because of Dijkstra's ordering property, the first time we reach the destination is guaranteed to be optimal. 6. Explore all four neighboring cells.

For each valid neighbor:

  • Compute height difference
  • Compute new effort:

$$newEffort = \max(currentEffort, heightDifference)$$ 7. Relax the edge.

If newEffort is smaller than the previously recorded effort for the neighbor:

  • Update dist
  • Push the new state into the heap
  1. Continue until the destination is reached.

Why It Works

Dijkstra's algorithm works whenever path costs are monotonic, meaning extending a path can never decrease its cost.

In this problem:

$$newEffort = \max(oldEffort, edgeWeight)$$

The effort can only stay the same or increase.

Therefore, once a node is removed from the min-heap, we have already found the minimum possible effort required to reach it. This guarantees correctness.

Python Solution

from typing import List
import heapq

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

        efforts = [[float("inf")] * cols for _ in range(rows)]
        efforts[0][0] = 0

        min_heap = [(0, 0, 0)]

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

        while min_heap:
            current_effort, row, col = heapq.heappop(min_heap)

            if row == rows - 1 and col == cols - 1:
                return current_effort

            if current_effort > efforts[row][col]:
                continue

            for dr, dc in directions:
                new_row = row + dr
                new_col = col + dc

                if 0 <= new_row < rows and 0 <= new_col < cols:
                    height_diff = abs(
                        heights[row][col] - heights[new_row][new_col]
                    )

                    new_effort = max(current_effort, height_diff)

                    if new_effort < efforts[new_row][new_col]:
                        efforts[new_row][new_col] = new_effort

                        heapq.heappush(
                            min_heap,
                            (new_effort, new_row, new_col)
                        )

        return 0

The implementation begins by determining the grid dimensions. We then create the efforts matrix, which stores the minimum effort needed to reach each cell.

A min-heap is used to process cells in increasing order of effort. This is the core requirement of Dijkstra's algorithm.

Each heap element contains:

  • Current minimum effort
  • Row index
  • Column index

For every popped cell, we attempt to move in four directions. The effort required to move into a neighboring cell is the maximum of:

  • Current path effort
  • Current edge height difference

If this produces a better result for the neighbor, we update the neighbor and push it into the heap.

The stale-state check:

if current_effort > efforts[row][col]:
    continue

prevents unnecessary processing of outdated heap entries.

The algorithm terminates as soon as the destination is removed from the heap, because that effort is guaranteed to be minimal.

Go Solution

package main

import (
	"container/heap"
	"math"
)

type State struct {
	effort int
	row    int
	col    int
}

type MinHeap []State

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i].effort < h[j].effort
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(State))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)

	item := old[n-1]
	*h = old[:n-1]

	return item
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func minimumEffortPath(heights [][]int) int {
	rows := len(heights)
	cols := len(heights[0])

	efforts := make([][]int, rows)

	for i := 0; i < rows; i++ {
		efforts[i] = make([]int, cols)

		for j := 0; j < cols; j++ {
			efforts[i][j] = math.MaxInt32
		}
	}

	efforts[0][0] = 0

	minHeap := &MinHeap{}
	heap.Init(minHeap)

	heap.Push(minHeap, State{0, 0, 0})

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	for minHeap.Len() > 0 {
		current := heap.Pop(minHeap).(State)

		currentEffort := current.effort
		row := current.row
		col := current.col

		if row == rows-1 && col == cols-1 {
			return currentEffort
		}

		if currentEffort > efforts[row][col] {
			continue
		}

		for _, dir := range directions {
			newRow := row + dir[0]
			newCol := col + dir[1]

			if newRow >= 0 && newRow < rows &&
				newCol >= 0 && newCol < cols {

				heightDiff := abs(
					heights[row][col] - heights[newRow][newCol],
				)

				newEffort := max(currentEffort, heightDiff)

				if newEffort < efforts[newRow][newCol] {
					efforts[newRow][newCol] = newEffort

					heap.Push(
						minHeap,
						State{newEffort, newRow, newCol},
					)
				}
			}
		}
	}

	return 0
}

The Go solution follows the same algorithmic structure as the Python version. The largest difference is that Go requires an explicit heap implementation using the container/heap package.

A custom State struct stores:

  • Current effort
  • Row
  • Column

The heap interface requires implementing:

  • Len
  • Less
  • Swap
  • Push
  • Pop

Go does not provide built-in max or abs functions for integers, so helper functions are implemented manually.

The remainder of the logic mirrors the Python solution exactly.

Worked Examples

Example 1

heights =
[
  [1,2,2],
  [3,8,2],
  [5,3,5]
]

Expected answer: 2

Initial State

Cell Effort
(0,0) 0
others inf

Heap:

Effort Position
0 (0,0)

Step 1

Pop (0,0).

Neighbors:

Neighbor Difference New Effort
(1,0) |1-3| = 2 2
(0,1) |1-2| = 1 1

Update heap.

Heap:

Effort Position
1 (0,1)
2 (1,0)

Step 2

Pop (0,1).

Neighbors:

Neighbor Difference New Effort
(0,2) 0 1
(1,1) 6 6

Heap:

Effort Position
1 (0,2)
2 (1,0)
6 (1,1)

Step 3

Pop (0,2).

Neighbors:

Neighbor Difference New Effort
(1,2) 0 1

Heap:

Effort Position
1 (1,2)
2 (1,0)
6 (1,1)

Step 4

Pop (1,2).

Neighbors:

Neighbor Difference New Effort
(2,2) 3 3
(1,1) 6 6

Heap:

Effort Position
2 (1,0)
3 (2,2)
6 (1,1)

Step 5

Pop (1,0).

Neighbors:

Neighbor Difference New Effort
(2,0) 2 2

Heap:

Effort Position
2 (2,0)
3 (2,2)
6 (1,1)

Step 6

Pop (2,0).

Neighbors:

Neighbor Difference New Effort
(2,1) 2 2

Heap:

Effort Position
2 (2,1)
3 (2,2)
6 (1,1)

Step 7

Pop (2,1).

Neighbors:

Neighbor Difference New Effort
(2,2) 2 2

We improve (2,2) from 3 to 2.

Destination reached with minimum effort 2.

Example 2

[
  [1,2,3],
  [3,8,4],
  [5,3,5]
]

The optimal path is:

1 → 2 → 3 → 4 → 5

All consecutive differences are 1.

Maximum difference is:

1

Answer:

1

Example 3

[
  [1,2,1,1,1],
  [1,2,1,2,1],
  [1,2,1,2,1],
  [1,2,1,2,1],
  [1,1,1,2,1]
]

A path exists using only equal-height moves.

All edge differences are:

0

Therefore the minimum effort is:

0

Complexity Analysis

Measure Complexity Explanation
Time O(rows × cols × log(rows × cols)) Each cell may enter the heap multiple times
Space O(rows × cols) Distance matrix and heap storage

Let:

V = rows × cols

Each cell is a graph vertex.

Each cell has at most four edges, so:

E ≈ 4V

Dijkstra's algorithm using a binary heap runs in:

$$O((V + E)\log V)$$

Since E = O(V), this simplifies to:

$$O(V \log V)$$

Substituting V = rows × cols gives:

$$O(rows \times cols \times \log(rows \times cols))$$

The space complexity comes from:

  • The efforts matrix
  • The priority queue

Both scale linearly with the number of cells.

Test Cases

from typing import List

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        import heapq

        rows = len(heights)
        cols = len(heights[0])

        efforts = [[float("inf")] * cols for _ in range(rows)]
        efforts[0][0] = 0

        heap = [(0, 0, 0)]

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

        while heap:
            effort, r, c = heapq.heappop(heap)

            if r == rows - 1 and c == cols - 1:
                return effort

            if effort > efforts[r][c]:
                continue

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if 0 <= nr < rows and 0 <= nc < cols:
                    diff = abs(heights[r][c] - heights[nr][nc])

                    new_effort = max(effort, diff)

                    if new_effort < efforts[nr][nc]:
                        efforts[nr][nc] = new_effort
                        heapq.heappush(heap, (new_effort, nr, nc))

        return 0

solution = Solution()

assert solution.minimumEffortPath(
    [[1,2,2],[3,8,2],[5,3,5]]
) == 2  # Example 1

assert solution.minimumEffortPath(
    [[1,2,3],[3,8,4],[5,3,5]]
) == 1  # Example 2

assert solution.minimumEffortPath(
    [[1,2,1,1,1],
     [1,2,1,2,1],
     [1,2,1,2,1],
     [1,2,1,2,1],
     [1,1,1,2,1]]
) == 0  # Example 3

assert solution.minimumEffortPath(
    [[1]]
) == 0  # Single cell

assert solution.minimumEffortPath(
    [[1,10]]
) == 9  # Single row

assert solution.minimumEffortPath(
    [[1],[100]]
) == 99  # Single column

assert solution.minimumEffortPath(
    [[5,5],[5,5]]
) == 0  # Uniform heights

assert solution.minimumEffortPath(
    [[1,100,1,1,1]]
) == 99  # Unavoidable large jump

assert solution.minimumEffortPath(
    [[1,2,3],
     [2,3,4],
     [3,4,5]]
) == 1  # Smooth gradient

assert solution.minimumEffortPath(
    [[1,1000],
     [1,1]]
) == 0  # Better indirect path

Test Summary

Test Why
Example 1 Validates standard multi-path behavior
Example 2 Verifies minimum maximum edge logic
Example 3 Confirms zero-effort path handling
[[1]] Single-cell boundary case
[[1,10]] Single-row traversal
[[1],[100]] Single-column traversal
Uniform grid Ensures all-zero effort works
Large unavoidable jump Confirms maximum edge tracking
Smooth gradient Tests repeated small differences
Better indirect path Ensures algorithm avoids greedy local jumps

Edge Cases

Single Cell Grid

A grid containing only one cell is an important boundary case.

[[7]]

Since the start and destination are the same cell, no movement occurs. Therefore, the effort must be 0.

A buggy implementation might incorrectly attempt neighbor exploration or return infinity. Our implementation handles this naturally because the start node is immediately recognized as the destination.

Indirect Path Better Than Direct Path

Consider:

[
  [1,1000],
  [1,1]
]

The direct move right has effort:

999

But moving downward first avoids any height difference:

1 → 1 → 1

Effort becomes:

0

This case is important because greedy local decisions fail. The algorithm correctly explores alternative routes using the priority queue.

Large Height Differences

Heights can be as large as:

10^6

Therefore, edge differences can also be very large.

An incorrect implementation might overflow in some languages or incorrectly accumulate values as sums. Our algorithm only computes absolute differences and maximums, both of which safely fit inside standard integer ranges for Python and Go.

Multiple Heap Insertions for Same Cell

A cell may enter the heap multiple times with different effort values.

This is common in Dijkstra's algorithm.

Without the stale-state check:

if current_effort > efforts[row][col]:
    continue

the algorithm would still be correct but would perform unnecessary processing. The implementation safely skips outdated states while preserving correctness.