1631. Path with Minimum Effort - Explanation

Description

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 you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). 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.

Example 1:

Input: heights = [
    [1,1,1],
    [3,2,4],
    [2,5,4]
]

Output: 2

Explanation: The route of [1,1,2,4,4] has a maximum absolute difference of 2 in consecutive cells.

Example 2:

Input: heights = [
    [1,1,1],
    [1,1,2],
    [6,5,2]
]

Output: 1

Explanation: The route of [1,1,1,1,1,2,2] has a maximum absolute difference of 1 in consecutive cells.

Constraints:

row == heights.length
col == heights[i].length
1 <= row, col <= 100
1 <= heights[i][j].length <= 1,000,000 .

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Dijkstra's Algorithm - Finding shortest paths using a priority queue with modified cost function
Binary Search - Searching for the minimum feasible effort value
Depth First Search (DFS) - Checking path reachability under a given constraint
Union-Find / Disjoint Set Union (DSU) - Connecting components to determine reachability (Kruskal's approach)
2D Grid Traversal - Moving in four directions and handling grid boundaries

1. Dijkstra's Algorithm

Intuition

The effort of a path is defined as the maximum absolute difference between consecutive cells along that path. We want to minimize this maximum difference. Dijkstra's algorithm fits well because we can treat the "effort so far" as the cost and always expand the path with the smallest maximum effort. When we reach the destination, we have found the path with minimum effort.

Algorithm

Initialize a min-heap with (0, 0, 0) representing (effort, row, col) starting at the top-left cell.
Maintain a distance array where dist[r][c] stores the minimum effort to reach cell (r, c). Initialize all values to infinity except dist[0][0] = 0.
Pop the cell with the smallest effort from the heap. If it is the destination, return the effort.
For each of the four neighbors, calculate the new effort as the maximum of the current effort and the absolute height difference.
If this new effort is better than the recorded distance for the neighbor, update it and push the neighbor to the heap.
Continue until the destination is reached.

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        ROWS, COLS = len(heights), len(heights[0])
        minHeap = [[0, 0, 0]]  # [diff, row, col]
        visit = set()
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        while minHeap:
            diff, r, c = heapq.heappop(minHeap)

            if (r, c) in visit:
                continue

            visit.add((r, c))

            if (r, c) == (ROWS - 1, COLS - 1):
                return diff

            for dr, dc in directions:
                newR, newC = r + dr, c + dc
                if (
                    newR < 0 or newC < 0 or
                    newR >= ROWS or newC >= COLS or
                    (newR, newC) in visit
                ):
                    continue

                newDiff = max(diff, abs(heights[r][c] - heights[newR][newC]))
                heapq.heappush(minHeap, [newDiff, newR, newC])

        return 0

public class Solution {
    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length;
        int cols = heights[0].length;
        int[][] dist = new int[rows][cols];
        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dist[0][0] = 0;

        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        minHeap.offer(new int[]{0, 0, 0}); // {diff, row, col}

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

        while (!minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            int diff = curr[0], r = curr[1], c = curr[2];

            if (r == rows - 1 && c == cols - 1) return diff;
            if (dist[r][c] < diff) continue;

            for (int[] dir : directions) {
                int newR = r + dir[0], newC = c + dir[1];
                if (newR < 0 || newC < 0 || newR >= rows || newC >= cols) {
                    continue;
                }

                int newDiff = Math.max(diff, Math.abs(heights[r][c] - heights[newR][newC]));
                if (newDiff < dist[newR][newC]) {
                    dist[newR][newC] = newDiff;
                    minHeap.offer(new int[]{newDiff, newR, newC});
                }
            }
        }

        return 0;
    }
}

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int rows = heights.size(), cols = heights[0].size();
        vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX));
        dist[0][0] = 0;

        priority_queue<vector<int>, vector<vector<int>>, greater<>> minHeap;
        minHeap.push({0, 0, 0}); // {diff, row, col}

        vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!minHeap.empty()) {
            auto curr = minHeap.top();
            minHeap.pop();
            int diff = curr[0], r = curr[1], c = curr[2];

            if (r == rows - 1 && c == cols - 1) return diff;
            if (dist[r][c] < diff) continue;

            for (auto& dir : directions) {
                int newR = r + dir[0], newC = c + dir[1];
                if (newR < 0 || newC < 0 || newR >= rows || newC >= cols) {
                    continue;
                }

                int newDiff = max(diff, abs(heights[r][c] - heights[newR][newC]));
                if (newDiff < dist[newR][newC]) {
                    dist[newR][newC] = newDiff;
                    minHeap.push({newDiff, newR, newC});
                }
            }
        }

        return 0;
    }
};

class Solution {
    /**
     * @param {number[][]} heights
     * @return {number}
     */
    minimumEffortPath(heights) {
        const rows = heights.length;
        const cols = heights[0].length;
        const dist = Array.from({ length: rows }, () =>
            Array(cols).fill(Infinity),
        );
        dist[0][0] = 0;

        const minHeap = new MinPriorityQueue((a) => a[0]);
        minHeap.enqueue([0, 0, 0]); // [diff, row, col]

        const directions = [
            [0, 1],
            [0, -1],
            [1, 0],
            [-1, 0],
        ];

        while (!minHeap.isEmpty()) {
            const [diff, r, c] = minHeap.dequeue();

            if (r === rows - 1 && c === cols - 1) return diff;
            if (dist[r][c] < diff) continue;

            for (const [dr, dc] of directions) {
                const newR = r + dr;
                const newC = c + dc;
                if (newR < 0 || newC < 0 || newR >= rows || newC >= cols) {
                    continue;
                }

                const newDiff = Math.max(
                    diff,
                    Math.abs(heights[r][c] - heights[newR][newC]),
                );
                if (newDiff < dist[newR][newC]) {
                    dist[newR][newC] = newDiff;
                    minHeap.enqueue([newDiff, newR, newC]);
                }
            }
        }

        return 0;
    }
}

public class Solution {
    public int MinimumEffortPath(int[][] heights) {
        int rows = heights.Length, cols = heights[0].Length;
        var directions = new int[][] {
            new int[] { 0, 1 },
            new int[] { 0, -1 },
            new int[] { 1, 0 },
            new int[] { -1, 0 }
        };

        var minHeap = new PriorityQueue<(int diff, int r, int c), int>();
        var visited = new HashSet<(int, int)>();
        minHeap.Enqueue((0, 0, 0), 0);

        while (minHeap.Count > 0) {
            var current = minHeap.Dequeue();
            int diff = current.diff, r = current.r, c = current.c;

            if (visited.Contains((r, c))) continue;
            visited.Add((r, c));

            if (r == rows - 1 && c == cols - 1) {
                return diff;
            }

            foreach (var dir in directions) {
                int newR = r + dir[0];
                int newC = c + dir[1];

                if (newR < 0 || newC < 0 || newR >= rows || newC >= cols || visited.Contains((newR, newC))) {
                    continue;
                }

                int newDiff = Math.Max(diff, Math.Abs(heights[r][c] - heights[newR][newC]));
                minHeap.Enqueue((newDiff, newR, newC), newDiff);
            }
        }

        return 0;
    }
}

import (
    "container/heap"
)

type Item struct {
    diff, r, c int
}

type MinHeap []Item

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].diff < h[j].diff }
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.(Item)) }
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func minimumEffortPath(heights [][]int) int {
    rows, cols := len(heights), len(heights[0])
    dist := make([][]int, rows)
    for i := range dist {
        dist[i] = make([]int, cols)
        for j := range dist[i] {
            dist[i][j] = 1 << 31 - 1
        }
    }
    dist[0][0] = 0

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

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

    for minHeap.Len() > 0 {
        curr := heap.Pop(minHeap).(Item)
        diff, r, c := curr.diff, curr.r, curr.c

        if r == rows-1 && c == cols-1 {
            return diff
        }
        if dist[r][c] < diff {
            continue
        }

        for _, dir := range directions {
            newR, newC := r+dir[0], c+dir[1]
            if newR < 0 || newC < 0 || newR >= rows || newC >= cols {
                continue
            }

            newDiff := max(diff, abs(heights[r][c]-heights[newR][newC]))
            if newDiff < dist[newR][newC] {
                dist[newR][newC] = newDiff
                heap.Push(minHeap, Item{newDiff, newR, newC})
            }
        }
    }

    return 0
}

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
}

class Solution {
    fun minimumEffortPath(heights: Array<IntArray>): Int {
        val rows = heights.size
        val cols = heights[0].size
        val dist = Array(rows) { IntArray(cols) { Int.MAX_VALUE } }
        dist[0][0] = 0

        val directions = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))

        val minHeap = PriorityQueue<IntArray>(compareBy { it[0] })
        minHeap.offer(intArrayOf(0, 0, 0)) // [diff, row, col]

        while (minHeap.isNotEmpty()) {
            val (diff, r, c) = minHeap.poll()

            if (r == rows - 1 && c == cols - 1) return diff
            if (dist[r][c] < diff) continue

            for (dir in directions) {
                val newR = r + dir[0]
                val newC = c + dir[1]
                if (newR < 0 || newC < 0 || newR >= rows || newC >= cols) continue

                val newDiff = maxOf(diff, kotlin.math.abs(heights[r][c] - heights[newR][newC]))
                if (newDiff < dist[newR][newC]) {
                    dist[newR][newC] = newDiff
                    minHeap.offer(intArrayOf(newDiff, newR, newC))
                }
            }
        }

        return 0
    }
}

class Solution {
    func minimumEffortPath(_ heights: [[Int]]) -> Int {
        let rows = heights.count
        let cols = heights[0].count
        var dist = [[Int]](repeating: [Int](repeating: Int.max, count: cols), count: rows)
        dist[0][0] = 0

        let directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        var minHeap = [(Int, Int, Int)]() // (diff, row, col)
        minHeap.append((0, 0, 0))

        while !minHeap.isEmpty {
            minHeap.sort { $0.0 < $1.0 }
            let (diff, r, c) = minHeap.removeFirst()

            if r == rows - 1 && c == cols - 1 {
                return diff
            }
            if dist[r][c] < diff {
                continue
            }

            for dir in directions {
                let newR = r + dir[0]
                let newC = c + dir[1]
                if newR < 0 || newC < 0 || newR >= rows || newC >= cols {
                    continue
                }

                let newDiff = max(diff, abs(heights[r][c] - heights[newR][newC]))
                if newDiff < dist[newR][newC] {
                    dist[newR][newC] = newDiff
                    minHeap.append((newDiff, newR, newC))
                }
            }
        }

        return 0
    }
}

Time & Space Complexity

Time complexity: $O(m * n * \log (m * n))$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the given matrix.

2. Binary Search + DFS

Intuition

We can binary search on the answer. For a given effort limit, we check whether it is possible to reach the destination using only edges with absolute differences at most that limit. dfs explores if a valid path exists under the constraint. If a path exists, we try a smaller limit; otherwise, we try a larger one.

Algorithm

Binary search on the effort limit between 0 and 1,000,000 (the maximum possible difference).
For each candidate limit (mid), run a dfs from (0, 0) to check if we can reach (ROWS-1, COLS-1) using only edges with absolute difference at most mid.
In the dfs, mark cells as visited and only move to neighbors where the height difference is within the limit.
If the dfs reaches the destination, the limit is feasible. Record it and search for a smaller limit.
If the dfs fails, search for a larger limit.
Return the smallest feasible limit found.

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        ROWS, COLS = len(heights), len(heights[0])
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        def dfs(r, c, limit, visited):
            if r == ROWS - 1 and c == COLS - 1:
                return True

            visited.add((r, c))
            for dr, dc in directions:
                newR, newC = r + dr, c + dc
                if (newR < 0 or newC < 0 or
                    newR >= ROWS or newC >= COLS or
                    (newR, newC) in visited or
                    abs(heights[newR][newC] - heights[r][c]) > limit):
                    continue

                if dfs(newR, newC, limit, visited):
                    return True
            return False

        l, r = 0, 1000000
        res = r

        while l <= r:
            mid = (l + r) // 2
            if dfs(0, 0, mid, set()):
                res = mid
                r = mid - 1
            else:
                l = mid + 1

        return res

class Solution {
private:
    int ROWS, COLS;
    vector<vector<int>> heights;
    vector<vector<bool>> visited;
    vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        this->heights = heights;
        this->ROWS = heights.size();
        this->COLS = heights[0].size();
        this->visited = vector<vector<bool>>(ROWS, vector<bool>(COLS, false));

        int l = 0, r = 1'000'000, res = r;
        while (l <= r) {
            int mid = (l + r) / 2;
            for (auto& row : visited) {
                fill(row.begin(), row.end(), false);
            }
            if (dfs(0, 0, mid)) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }

private:
    bool dfs(int r, int c, int limit) {
        if (r == ROWS - 1 && c == COLS - 1) {
            return true;
        }

        visited[r][c] = true;
        for (const auto& dir : directions) {
            int newR = r + dir[0];
            int newC = c + dir[1];
            if (newR < 0 || newC < 0 || newR >= ROWS || newC >= COLS || visited[newR][newC]) {
                continue;
            }
            if (abs(heights[newR][newC] - heights[r][c]) > limit) {
                continue;
            }
            if (dfs(newR, newC, limit)) {
                return true;
            }
        }
        return false;
    }
};

class Solution {
    /**
     * @param {number[][]} heights
     * @return {number}
     */
    minimumEffortPath(heights) {
        const ROWS = heights.length;
        const COLS = heights[0].length;
        const directions = [
            [0, 1],
            [0, -1],
            [1, 0],
            [-1, 0],
        ];
        let visited = Array.from({ length: ROWS }, () =>
            Array(COLS).fill(false),
        );

        const dfs = (r, c, limit) => {
            if (r === ROWS - 1 && c === COLS - 1) {
                return true;
            }

            visited[r][c] = true;
            for (const [dr, dc] of directions) {
                const newR = r + dr;
                const newC = c + dc;

                if (
                    newR < 0 ||
                    newC < 0 ||
                    newR >= ROWS ||
                    newC >= COLS ||
                    visited[newR][newC]
                ) {
                    continue;
                }
                if (Math.abs(heights[newR][newC] - heights[r][c]) > limit) {
                    continue;
                }
                if (dfs(newR, newC, limit)) {
                    return true;
                }
            }
            return false;
        };

        let l = 0,
            r = 1_000_000,
            res = r;
        while (l <= r) {
            const mid = Math.floor((l + r) / 2);
            for (const row of visited) {
                row.fill(false);
            }
            if (dfs(0, 0, mid)) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }
}

class Solution {
    private val directions = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))

    fun minimumEffortPath(heights: Array<IntArray>): Int {
        val rows = heights.size
        val cols = heights[0].size

        fun dfs(r: Int, c: Int, limit: Int, visited: Array<BooleanArray>): Boolean {
            if (r == rows - 1 && c == cols - 1) return true

            visited[r][c] = true
            for (dir in directions) {
                val newR = r + dir[0]
                val newC = c + dir[1]
                if (newR < 0 || newC < 0 || newR >= rows || newC >= cols || visited[newR][newC]) continue
                if (kotlin.math.abs(heights[newR][newC] - heights[r][c]) > limit) continue
                if (dfs(newR, newC, limit, visited)) return true
            }
            return false
        }

        var l = 0
        var r = 1000000
        var res = r

        while (l <= r) {
            val mid = (l + r) / 2
            val visited = Array(rows) { BooleanArray(cols) }
            if (dfs(0, 0, mid, visited)) {
                res = mid
                r = mid - 1
            } else {
                l = mid + 1
            }
        }

        return res
    }
}

class Solution {
    func minimumEffortPath(_ heights: [[Int]]) -> Int {
        let rows = heights.count
        let cols = heights[0].count
        let directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        func dfs(_ r: Int, _ c: Int, _ limit: Int, _ visited: inout [[Bool]]) -> Bool {
            if r == rows - 1 && c == cols - 1 {
                return true
            }

            visited[r][c] = true
            for dir in directions {
                let newR = r + dir[0]
                let newC = c + dir[1]
                if newR < 0 || newC < 0 || newR >= rows || newC >= cols || visited[newR][newC] {
                    continue
                }
                if abs(heights[newR][newC] - heights[r][c]) > limit {
                    continue
                }
                if dfs(newR, newC, limit, &visited) {
                    return true
                }
            }
            return false
        }

        var l = 0
        var r = 1000000
        var res = r

        while l <= r {
            let mid = (l + r) / 2
            var visited = [[Bool]](repeating: [Bool](repeating: false, count: cols), count: rows)
            if dfs(0, 0, mid, &visited) {
                res = mid
                r = mid - 1
            } else {
                l = mid + 1
            }
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(m * n * \log (m * n))$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the given matrix.

3. Kruskal's Algorithm

Intuition

We can view the grid as a graph where each cell is a node and edges connect adjacent cells with weights equal to the absolute height difference. The problem becomes finding the path from top-left to bottom-right that minimizes the maximum edge weight. Kruskal's algorithm processes edges in sorted order, and we stop as soon as the source and destination become connected. The last edge added determines the minimum effort.

Algorithm

Create a list of all edges between adjacent cells, where each edge stores (weight, cell1, cell2). Map each cell to a unique index.
Sort edges by weight in ascending order.
Initialize a Disjoint Set Union (DSU) data structure.
Process edges one by one. For each edge, union the two cells.
After each union, check if the top-left cell (index 0) and bottom-right cell are connected.
If connected, return the current edge weight as the answer.
If the grid has only one cell, return 0.

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] < self.Size[pv]:
            pu, pv = pv, pu
        self.Size[pu] += self.Size[pv]
        self.Parent[pv] = pu
        return True


class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        ROWS, COLS = len(heights), len(heights[0])
        edges = []
        for r in range(ROWS):
            for c in range(COLS):
                if r + 1 < ROWS:
                    edges.append((abs(heights[r][c] - heights[r + 1][c]), r * COLS + c, (r + 1) * COLS + c))
                if c + 1 < COLS:
                    edges.append((abs(heights[r][c] - heights[r][c + 1]), r * COLS + c, r * COLS + c + 1))

        edges.sort()
        dsu = DSU(ROWS * COLS)
        for weight, u, v in edges:
            dsu.union(u, v)
            if dsu.find(0) == dsu.find(ROWS * COLS - 1):
                return weight
        return 0

class DSU {
private:
    vector<int> Parent, Size;

public:
    DSU(int n) {
        Parent.resize(n + 1);
        Size.resize(n + 1, 1);
        for (int i = 0; i <= n; i++) {
            Parent[i] = i;
        }
    }

    int find(int node) {
        if (Parent[node] != node) {
            Parent[node] = find(Parent[node]);
        }
        return Parent[node];
    }

    bool unionSets(int u, int v) {
        int pu = find(u);
        int pv = find(v);
        if (pu == pv) {
            return false;
        }
        if (Size[pu] < Size[pv]) {
            swap(pu, pv);
        }
        Size[pu] += Size[pv];
        Parent[pv] = pu;
        return true;
    }
};

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int ROWS = heights.size();
        int COLS = heights[0].size();
        vector<tuple<int, int, int>> edges;
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (r + 1 < ROWS) {
                    edges.push_back({abs(heights[r][c] - heights[r + 1][c]), r * COLS + c, (r + 1) * COLS + c});
                }
                if (c + 1 < COLS) {
                    edges.push_back({abs(heights[r][c] - heights[r][c + 1]), r * COLS + c, r * COLS + c + 1});
                }
            }
        }

        sort(edges.begin(), edges.end());
        DSU dsu(ROWS * COLS);
        for (auto& edge : edges) {
            int weight, u, v;
            tie(weight, u, v) = edge;
            dsu.unionSets(u, v);
            if (dsu.find(0) == dsu.find(ROWS * COLS - 1)) {
                return weight;
            }
        }
        return 0;
    }
};

class DSU {
    /**
     * @constructor
     * @param {number} n
     */
    constructor(n) {
        this.Parent = Array.from({ length: n + 1 }, (_, i) => i);
        this.Size = Array(n + 1).fill(1);
    }

    /**
     * @param {number} node
     * @return {number}
     */
    find(node) {
        if (this.Parent[node] !== node) {
            this.Parent[node] = this.find(this.Parent[node]);
        }
        return this.Parent[node];
    }

    /**
     * @param {number} u
     * @param {number} v
     * @return {boolean}
     */
    union(u, v) {
        let pu = this.find(u),
            pv = this.find(v);
        if (pu === pv) return false;
        if (this.Size[pu] < this.Size[pv]) [pu, pv] = [pv, pu];
        this.Size[pu] += this.Size[pv];
        this.Parent[pv] = pu;
        return true;
    }
}

class Solution {
    /**
     * @param {number[][]} heights
     * @return {number}
     */
    minimumEffortPath(heights) {
        const ROWS = heights.length;
        const COLS = heights[0].length;
        const edges = [];
        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                if (r + 1 < ROWS) {
                    edges.push([
                        Math.abs(heights[r][c] - heights[r + 1][c]),
                        r * COLS + c,
                        (r + 1) * COLS + c,
                    ]);
                }
                if (c + 1 < COLS) {
                    edges.push([
                        Math.abs(heights[r][c] - heights[r][c + 1]),
                        r * COLS + c,
                        r * COLS + c + 1,
                    ]);
                }
            }
        }

        edges.sort((a, b) => a[0] - b[0]);
        const dsu = new DSU(ROWS * COLS);
        for (const [weight, u, v] of edges) {
            dsu.union(u, v);
            if (dsu.find(0) === dsu.find(ROWS * COLS - 1)) {
                return weight;
            }
        }
        return 0;
    }
}

public class DSU {
    private int[] parent;
    private int[] size;

    public DSU(int n) {
        parent = new int[n + 1];
        size = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int Find(int node) {
        if (parent[node] != node) {
            parent[node] = Find(parent[node]);
        }
        return parent[node];
    }

    public bool Union(int u, int v) {
        int pu = Find(u);
        int pv = Find(v);
        if (pu == pv) return false;
        if (size[pu] < size[pv]) {
            (pu, pv) = (pv, pu);
        }
        size[pu] += size[pv];
        parent[pv] = pu;
        return true;
    }
}

public class Solution {
    public int MinimumEffortPath(int[][] heights) {
        int rows = heights.Length;
        int cols = heights[0].Length;
        List<(int, int, int)> edges = new List<(int, int, int)>();

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int id = r * cols + c;
                if (r + 1 < rows) {
                    int downId = (r + 1) * cols + c;
                    int diff = Math.Abs(heights[r][c] - heights[r + 1][c]);
                    edges.Add((diff, id, downId));
                }
                if (c + 1 < cols) {
                    int rightId = r * cols + (c + 1);
                    int diff = Math.Abs(heights[r][c] - heights[r][c + 1]);
                    edges.Add((diff, id, rightId));
                }
            }
        }

        edges.Sort((a, b) => a.Item1.CompareTo(b.Item1));
        DSU dsu = new DSU(rows * cols);

        foreach (var (weight, u, v) in edges) {
            dsu.Union(u, v);
            if (dsu.Find(0) == dsu.Find(rows * cols - 1)) {
                return weight;
            }
        }

        return 0;
    }
}

type DSU struct {
    parent []int
    size   []int
}

func NewDSU(n int) *DSU {
    parent := make([]int, n+1)
    size := make([]int, n+1)
    for i := 0; i <= n; i++ {
        parent[i] = i
        size[i] = 1
    }
    return &DSU{parent, size}
}

func (d *DSU) Find(node int) int {
    if d.parent[node] != node {
        d.parent[node] = d.Find(d.parent[node])
    }
    return d.parent[node]
}

func (d *DSU) Union(u, v int) bool {
    pu, pv := d.Find(u), d.Find(v)
    if pu == pv {
        return false
    }
    if d.size[pu] < d.size[pv] {
        pu, pv = pv, pu
    }
    d.size[pu] += d.size[pv]
    d.parent[pv] = pu
    return true
}

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

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if r+1 < rows {
                diff := abs(heights[r][c] - heights[r+1][c])
                edges = append(edges, []int{diff, r*cols + c, (r+1)*cols + c})
            }
            if c+1 < cols {
                diff := abs(heights[r][c] - heights[r][c+1])
                edges = append(edges, []int{diff, r*cols + c, r*cols + c + 1})
            }
        }
    }

    sort.Slice(edges, func(i, j int) bool {
        return edges[i][0] < edges[j][0]
    })

    dsu := NewDSU(rows * cols)
    for _, edge := range edges {
        weight, u, v := edge[0], edge[1], edge[2]
        dsu.Union(u, v)
        if dsu.Find(0) == dsu.Find(rows*cols-1) {
            return weight
        }
    }

    return 0
}

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

class DSU(n: Int) {
    private val parent = IntArray(n + 1) { it }
    private val size = IntArray(n + 1) { 1 }

    fun find(node: Int): Int {
        if (parent[node] != node) {
            parent[node] = find(parent[node])
        }
        return parent[node]
    }

    fun union(u: Int, v: Int): Boolean {
        var pu = find(u)
        var pv = find(v)
        if (pu == pv) return false
        if (size[pu] < size[pv]) {
            val temp = pu
            pu = pv
            pv = temp
        }
        size[pu] += size[pv]
        parent[pv] = pu
        return true
    }
}

class Solution {
    fun minimumEffortPath(heights: Array<IntArray>): Int {
        val rows = heights.size
        val cols = heights[0].size
        val edges = mutableListOf<IntArray>()

        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (r + 1 < rows) {
                    val diff = kotlin.math.abs(heights[r][c] - heights[r + 1][c])
                    edges.add(intArrayOf(diff, r * cols + c, (r + 1) * cols + c))
                }
                if (c + 1 < cols) {
                    val diff = kotlin.math.abs(heights[r][c] - heights[r][c + 1])
                    edges.add(intArrayOf(diff, r * cols + c, r * cols + c + 1))
                }
            }
        }

        edges.sortBy { it[0] }
        val dsu = DSU(rows * cols)

        for ((weight, u, v) in edges) {
            dsu.union(u, v)
            if (dsu.find(0) == dsu.find(rows * cols - 1)) {
                return weight
            }
        }

        return 0
    }
}

class DSU {
    var parent: [Int]
    var size: [Int]

    init(_ n: Int) {
        parent = Array(0...n)
        size = [Int](repeating: 1, count: n + 1)
    }

    func find(_ node: Int) -> Int {
        if parent[node] != node {
            parent[node] = find(parent[node])
        }
        return parent[node]
    }

    func union(_ u: Int, _ v: Int) -> Bool {
        var pu = find(u)
        var pv = find(v)
        if pu == pv {
            return false
        }
        if size[pu] < size[pv] {
            swap(&pu, &pv)
        }
        size[pu] += size[pv]
        parent[pv] = pu
        return true
    }
}

class Solution {
    func minimumEffortPath(_ heights: [[Int]]) -> Int {
        let rows = heights.count
        let cols = heights[0].count
        var edges = [(Int, Int, Int)]()

        for r in 0..<rows {
            for c in 0..<cols {
                if r + 1 < rows {
                    let diff = abs(heights[r][c] - heights[r + 1][c])
                    edges.append((diff, r * cols + c, (r + 1) * cols + c))
                }
                if c + 1 < cols {
                    let diff = abs(heights[r][c] - heights[r][c + 1])
                    edges.append((diff, r * cols + c, r * cols + c + 1))
                }
            }
        }

        edges.sort { $0.0 < $1.0 }
        let dsu = DSU(rows * cols)

        for (weight, u, v) in edges {
            _ = dsu.union(u, v)
            if dsu.find(0) == dsu.find(rows * cols - 1) {
                return weight
            }
        }

        return 0
    }
}

Time & Space Complexity

Time complexity: $O(m * n * \log (m * n))$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the given matrix.

4. Shortest Path Faster Algorithm

Intuition

SPFA can also solve this problem by treating effort as the distance metric. We use a queue to process cells and update their minimum effort when a better path is found. Unlike Dijkstra's, SPFA does not require a priority queue, trading off guaranteed optimal ordering for simplicity and potential efficiency on some inputs.

Algorithm

Initialize a dist array with infinity for all cells except dist[0] = 0 for the starting cell.
Use a queue and add the starting cell. Track which cells are currently in the queue.
Dequeue a cell and mark it as not in the queue.
For each neighbor, compute the new effort as max(current effort, height difference).
If the new effort is less than the neighbor's recorded effort, update it. If the neighbor is not in the queue, add it.
Continue until the queue is empty and return dist for the bottom-right cell.

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        ROWS, COLS = len(heights), len(heights[0])
        dist = [float('inf')] * (ROWS * COLS)
        dist[0] = 0
        in_queue = [False] * (ROWS * COLS)

        def index(r, c):
            return r * COLS + c

        queue = deque([0])
        in_queue[0] = True
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        while queue:
            u = queue.popleft()
            in_queue[u] = False
            r, c = divmod(u, COLS)

            for dr, dc in directions:
                newR, newC = r + dr, c + dc
                if 0 <= newR < ROWS and 0 <= newC < COLS:
                    v = index(newR, newC)
                    weight = abs(heights[r][c] - heights[newR][newC])
                    new_dist = max(dist[u], weight)
                    if new_dist < dist[v]:
                        dist[v] = new_dist
                        if not in_queue[v]:
                            queue.append(v)
                            in_queue[v] = True

        return dist[ROWS * COLS - 1]

public class Solution {
    public int minimumEffortPath(int[][] heights) {
        int ROWS = heights.length, COLS = heights[0].length;
        int[] dist = new int[ROWS * COLS];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;

        boolean[] inQueue = new boolean[ROWS * COLS];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        inQueue[0] = true;

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

        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false;

            int r = u / COLS, c = u % COLS;

            for (int[] dir : directions) {
                int newR = r + dir[0], newC = c + dir[1];
                if (newR >= 0 && newC >= 0 && newR < ROWS && newC < COLS) {
                    int v = newR * COLS + newC;
                    int weight = Math.abs(heights[r][c] - heights[newR][newC]);
                    int newDist = Math.max(dist[u], weight);
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        if (!inQueue[v]) {
                            queue.offer(v);
                            inQueue[v] = true;
                        }
                    }
                }
            }
        }

        return dist[ROWS * COLS - 1];
    }
}

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int ROWS = heights.size(), COLS = heights[0].size();
        vector<int> dist(ROWS * COLS, INT_MAX);
        dist[0] = 0;

        vector<bool> inQueue(ROWS * COLS, false);
        queue<int> q;
        q.push(0);
        inQueue[0] = true;

        vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            inQueue[u] = false;

            int r = u / COLS, c = u % COLS;

            for (const auto& dir : directions) {
                int newR = r + dir[0], newC = c + dir[1];
                if (newR >= 0 && newC >= 0 && newR < ROWS && newC < COLS) {
                    int v = newR * COLS + newC;
                    int weight = abs(heights[r][c] - heights[newR][newC]);
                    int newDist = max(dist[u], weight);
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        if (!inQueue[v]) {
                            q.push(v);
                            inQueue[v] = true;
                        }
                    }
                }
            }
        }

        return dist[ROWS * COLS - 1];
    }
};

class Solution {
    /**
     * @param {number[][]} heights
     * @return {number}
     */
    minimumEffortPath(heights) {
        const ROWS = heights.length,
            COLS = heights[0].length;
        const dist = Array(ROWS * COLS).fill(Infinity);
        dist[0] = 0;

        const inQueue = Array(ROWS * COLS).fill(false);
        const queue = new Queue();
        queue.push(0);
        inQueue[0] = true;

        const directions = [
            [0, 1],
            [0, -1],
            [1, 0],
            [-1, 0],
        ];

        while (!queue.isEmpty()) {
            const u = queue.pop();
            inQueue[u] = false;

            const r = Math.floor(u / COLS),
                c = u % COLS;
            for (const [dr, dc] of directions) {
                const newR = r + dr,
                    newC = c + dc;
                if (newR >= 0 && newC >= 0 && newR < ROWS && newC < COLS) {
                    const v = newR * COLS + newC;
                    const weight = Math.abs(
                        heights[r][c] - heights[newR][newC],
                    );
                    const newDist = Math.max(dist[u], weight);
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        if (!inQueue[v]) {
                            queue.push(v);
                            inQueue[v] = true;
                        }
                    }
                }
            }
        }

        return dist[ROWS * COLS - 1];
    }
}

public class Solution {
    public int MinimumEffortPath(int[][] heights) {
        int rows = heights.Length;
        int cols = heights[0].Length;
        int[] dist = Enumerable.Repeat(int.MaxValue, rows * cols).ToArray();
        bool[] inQueue = new bool[rows * cols];
        dist[0] = 0;

        int Index(int r, int c) => r * cols + c;

        Queue<int> queue = new Queue<int>();
        queue.Enqueue(0);
        inQueue[0] = true;

        int[][] directions = new int[][] {
            new int[] {0, 1}, new int[] {0, -1},
            new int[] {1, 0}, new int[] {-1, 0}
        };

        while (queue.Count > 0) {
            int u = queue.Dequeue();
            inQueue[u] = false;
            int r = u / cols, c = u % cols;

            foreach (var dir in directions) {
                int newR = r + dir[0], newC = c + dir[1];
                if (newR >= 0 && newR < rows && newC >= 0 && newC < cols) {
                    int v = Index(newR, newC);
                    int weight = Math.Abs(heights[r][c] - heights[newR][newC]);
                    int newDist = Math.Max(dist[u], weight);
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        if (!inQueue[v]) {
                            queue.Enqueue(v);
                            inQueue[v] = true;
                        }
                    }
                }
            }
        }

        return dist[rows * cols - 1];
    }
}

func minimumEffortPath(heights [][]int) int {
    rows, cols := len(heights), len(heights[0])
    dist := make([]int, rows*cols)
    for i := range dist {
        dist[i] = 1 << 31 - 1
    }
    dist[0] = 0

    inQueue := make([]bool, rows*cols)
    queue := []int{0}
    inQueue[0] = true

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

    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        inQueue[u] = false

        r, c := u/cols, u%cols

        for _, dir := range directions {
            newR, newC := r+dir[0], c+dir[1]
            if newR >= 0 && newC >= 0 && newR < rows && newC < cols {
                v := newR*cols + newC
                weight := abs(heights[r][c] - heights[newR][newC])
                newDist := max(dist[u], weight)
                if newDist < dist[v] {
                    dist[v] = newDist
                    if !inQueue[v] {
                        queue = append(queue, v)
                        inQueue[v] = true
                    }
                }
            }
        }
    }

    return dist[rows*cols-1]
}

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
}

class Solution {
    fun minimumEffortPath(heights: Array<IntArray>): Int {
        val rows = heights.size
        val cols = heights[0].size
        val dist = IntArray(rows * cols) { Int.MAX_VALUE }
        dist[0] = 0

        val inQueue = BooleanArray(rows * cols)
        val queue = ArrayDeque<Int>()
        queue.add(0)
        inQueue[0] = true

        val directions = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))

        while (queue.isNotEmpty()) {
            val u = queue.removeFirst()
            inQueue[u] = false

            val r = u / cols
            val c = u % cols

            for (dir in directions) {
                val newR = r + dir[0]
                val newC = c + dir[1]
                if (newR in 0 until rows && newC in 0 until cols) {
                    val v = newR * cols + newC
                    val weight = kotlin.math.abs(heights[r][c] - heights[newR][newC])
                    val newDist = maxOf(dist[u], weight)
                    if (newDist < dist[v]) {
                        dist[v] = newDist
                        if (!inQueue[v]) {
                            queue.add(v)
                            inQueue[v] = true
                        }
                    }
                }
            }
        }

        return dist[rows * cols - 1]
    }
}

class Solution {
    func minimumEffortPath(_ heights: [[Int]]) -> Int {
        let rows = heights.count
        let cols = heights[0].count
        var dist = [Int](repeating: Int.max, count: rows * cols)
        dist[0] = 0

        var inQueue = [Bool](repeating: false, count: rows * cols)
        var queue = [0]
        inQueue[0] = true

        let directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        while !queue.isEmpty {
            let u = queue.removeFirst()
            inQueue[u] = false

            let r = u / cols
            let c = u % cols

            for dir in directions {
                let newR = r + dir[0]
                let newC = c + dir[1]
                if newR >= 0 && newC >= 0 && newR < rows && newC < cols {
                    let v = newR * cols + newC
                    let weight = abs(heights[r][c] - heights[newR][newC])
                    let newDist = max(dist[u], weight)
                    if newDist < dist[v] {
                        dist[v] = newDist
                        if !inQueue[v] {
                            queue.append(v)
                            inQueue[v] = true
                        }
                    }
                }
            }
        }

        return dist[rows * cols - 1]
    }
}

Time & Space Complexity

Time complexity:
- $O(m * n)$ time in average case.
- $O(m ^ 2 * n ^ 2)$ time in worst case.
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the given matrix.

Common Pitfalls

Summing Differences Instead of Taking Maximum

The effort of a path is defined as the maximum absolute difference along the path, not the sum. Using addition instead of max() when computing the new effort will give incorrect results. Always compute newEffort = max(currentEffort, abs(height[current] - height[neighbor])).

Confusing Single-Cell Grids

When the grid has only one cell, the answer is 0 since we are already at the destination. Some implementations may fail to handle this edge case, especially when the algorithm expects at least one move. Check for ROWS == 1 && COLS == 1 as a base case or ensure your algorithm naturally returns 0.

Incorrect Distance Initialization

In Dijkstra's algorithm, all distances should be initialized to infinity except for the starting cell which should be 0. Some implementations mistakenly initialize all distances to zero or forget to set the starting distance, causing the algorithm to skip valid relaxations or produce incorrect minimum efforts.