This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#1631) before relying on it.

Path With Minimum Effort

An interactive visualization of Dijkstra's algorithm on a grid, where edge weights are absolute height differences and the goal is to minimize the maximum effort along the path from top-left to bottom-right.

Shortest Path LeetCode 1631 ↗ Medium

The Problem

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell (0, 0) and hope to travel to the bottom-right cell (rows-1, columns-1).

You can move up, down, left, or right, and you wish to find a route that requires the minimum effort. A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Interactive Visualization

Grid (rows on separate lines, comma-separated)

Preset

Speed:

Grid Visualization

Unvisited

Processing

In Queue

Finalized

Optimal Path

Priority Queue: empty

Code

fun minimumEffortPath(heights: Array<IntArray>): Int {    val rows = heights.size; val cols = heights[0].size    val effort = Array(rows) { IntArray(cols) { Int.MAX_VALUE } }    effort[0][0] = 0    val pq = PriorityQueue<Triple<Int,Int,Int>>(compareBy { it.first })    pq.add(Triple(0, 0, 0))  // (effort, row, col)    while (pq.isNotEmpty()) {        val (e, r, c) = pq.poll()        if (r == rows - 1 && c == cols - 1)            return e        if (e > effort[r][c])            continue        for ((dr, dc) in arrayOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1)) {            val nr = r + dr; val nc = c + dc            if (nr in 0 until rows && nc in 0 until cols) {                val newE = maxOf(e, Math.abs(heights[r][c] - heights[nr][nc]))                if (newE < effort[nr][nc]) {                    effort[nr][nc] = newE                    pq.add(Triple(newE, nr, nc)) } } } } }

def minimumEffortPath(heights):    rows, cols = len(heights), len(heights[0])    effort = [[float('inf')] * cols for _ in range(rows)]    effort[0][0] = 0    pq = [(0, 0, 0)]  # (effort, row, col)    while pq:        e, r, c = heapq.heappop(pq)        if r == rows - 1 and c == cols - 1:            return e        if e > effort[r][c]:            continue        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:            nr, nc = r + dr, c + dc            if 0 <= nr < rows and 0 <= nc < cols:                new_e = max(e, abs(heights[r][c] - heights[nr][nc]))                if new_e < effort[nr][nc]:                    effort[nr][nc] = new_e                    heapq.heappush(pq, (new_e, nr, nc))

Status

Press Step or Play to begin.

How It Works

Key Insight

This problem is a shortest-path problem on a grid, but with a twist: instead of summing edge weights, we want to minimize the maximum absolute height difference along the path. We can solve this using Dijkstra's algorithm, where the "distance" to each cell is the minimum possible maximum effort to reach it. The priority queue always processes the cell with the smallest effort first, guaranteeing optimality.

The Algorithm

Initialize: set effort[0][0] = 0 and push (0, 0, 0) onto the priority queue.
Each iteration: pop the cell (e, r, c) with the smallest effort from the priority queue.
Early exit: if (r, c) is the destination (rows-1, cols-1), return e as the answer.
Skip stale: if e > effort[r][c], this entry is outdated — skip it.
Relax neighbors: for each of the 4 adjacent cells, compute new_e = max(e, |heights[r][c] - heights[nr][nc]|). If new_e < effort[nr][nc], update and push onto the queue.
Guaranteed: Dijkstra ensures the first time we pop the destination, we have the optimal answer.

Complexity

Time O(mn log(mn))

Space O(mn)

Each cell can be pushed to the priority queue at most 4 times (once per neighbor), and each heap operation costs O(log(mn)). The effort array uses O(mn) space.