Path With Minimum Effort

Description

You are a hiker preparing for an upcoming hike through mountainous terrain represented as a two-dimensional grid. The grid heights has dimensions rows × columns, where heights[row][col] gives the elevation at cell (row, col).

You start at the top-left cell (0, 0) and need to reach the bottom-right cell (rows - 1, columns - 1). From any cell, you may move in four directions: up, down, left, or right (no diagonal moves).

A route's effort is defined as the maximum absolute difference in height between any two consecutive cells along that route. For example, if you travel through cells with heights [1, 3, 5, 3], the effort is max(|1-3|, |3-5|, |5-3|) = 2.

Your task is to find the route from start to finish that minimizes this effort value. Return the minimum effort required.

Note that the effort is NOT the total sum of height differences — it is the single largest height jump encountered along the entire path. You want this largest jump to be as small as possible.

3x3 grid showing heights with two paths highlighted: a suboptimal path with effort 3 and the optimal path with effort 2

Examples

Example 1

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

Output: 2

Explanation: Consider the route (0,0) → (1,0) → (2,0) → (2,1) → (2,2) with heights [1, 3, 5, 3, 5]. The consecutive differences are |1−3| = 2, |3−5| = 2, |5−3| = 2, |3−5| = 2. The maximum difference is 2, so the effort is 2.

Compare this to the route (0,0) → (0,1) → (0,2) → (1,2) → (2,2) with heights [1, 2, 2, 2, 5]. The differences are 1, 0, 0, 3, giving effort = 3. The first path's effort of 2 is smaller, and no path achieves effort less than 2.

Example 2

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

Output: 1

Explanation: The route (0,0) → (0,1) → (0,2) → (1,2) → (2,2) follows heights [1, 2, 3, 4, 5]. The consecutive differences are all exactly 1: |1−2| = 1, |2−3| = 1, |3−4| = 1, |4−5| = 1. The effort is max(1, 1, 1, 1) = 1. No path can achieve effort 0 because every path from (0,0) must eventually increase in height.

Example 3

Input: heights = [[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]]

Output: 0

Explanation: The route can snake through all cells with height 1 without ever stepping on a cell of height 2. Following the path along the left column down, then across the bottom row, then up through the middle, we only pass through cells of height 1. All consecutive differences are 0, giving effort = 0.

Constraints

rows == heights.length
columns == heights[i].length
1 ≤ rows, columns ≤ 100
1 ≤ heights[i][j] ≤ 10^6

Editorial

Brute Force

Intuition

The most natural approach is to try every possible path from the start to the destination and pick the one with the least effort.

Imagine you are actually a hiker looking at a trail map. You start at the trailhead (top-left) and want to reach the campsite (bottom-right). One way to find the easiest route is to literally walk every possible trail, note the steepest single climb on each trail, and then choose the trail where that steepest climb was the mildest.

We implement this using Depth-First Search (DFS) with backtracking. At each cell, we try all four directions. We keep a visited set to prevent revisiting cells within the same path (avoiding infinite loops). Along the way, we track the running effort — the maximum height difference seen so far on the current path. When we reach the destination, we compare this path's effort to the best effort found so far.

To avoid exploring hopeless paths, we add a simple pruning rule: if the running effort already exceeds the best known effort, we stop exploring that path immediately.

Step-by-Step Explanation

Let's trace through with heights = [[1, 2, 2], [3, 8, 2], [5, 3, 5]]. Start = (0,0), End = (2,2).

Step 1: Begin DFS at (0,0) with effort = 0. Mark (0,0) visited.

Step 2: Move right to (0,1). Height difference |1−2| = 1. Effort = max(0, 1) = 1. Mark (0,1) visited.

Step 3: Move right to (0,2). Height difference |2−2| = 0. Effort = max(1, 0) = 1. Mark (0,2) visited.

Step 4: Move down to (1,2). Height difference |2−2| = 0. Effort = max(1, 0) = 1. Mark (1,2) visited.

Step 5: Move down to (2,2) — destination! Height difference |2−5| = 3. Effort = max(1, 3) = 3. Record min_effort = 3.

Step 6: Backtrack all the way to (0,0). Unmark all visited cells. Try a different direction: move down to (1,0). Height difference |1−3| = 2. Effort = max(0, 2) = 2. Since 2 < min_effort(3), continue.

Step 7: Move down to (2,0). Height difference |3−5| = 2. Effort = max(2, 2) = 2. Still ≤ 3, continue.

Step 8: Move right to (2,1). Height difference |5−3| = 2. Effort = max(2, 2) = 2. Continue.

Step 9: Move right to (2,2) — destination! Height difference |3−5| = 2. Effort = max(2, 2) = 2. Update min_effort = min(3, 2) = 2.

Step 10: Continue exploring remaining paths. All other paths yield effort ≥ 2. Final answer: 2.

Brute Force DFS — Exploring All Paths — Watch how DFS explores one complete path to the destination, records its effort, then backtracks and tries an alternative path with lower effort.

Algorithm

If the grid has only one cell, return 0.
Initialize min_effort = ∞ and a 2D visited array (all false).
Define a recursive DFS function dfs(row, col, effort):
- If (row, col) is the destination, update min_effort = min(min_effort, effort) and return.
- For each of the 4 directions (up, down, left, right):
  - Compute (nr, nc) = neighbor coordinates.
  - If in bounds and not visited:
    - Compute new_effort = max(effort, |heights[row][col] - heights[nr][nc]|).
    - Prune: If new_effort ≥ min_effort, skip (cannot improve).
    - Mark (nr, nc) as visited, recurse with dfs(nr, nc, new_effort), then unmark.
Mark (0, 0) as visited and call dfs(0, 0, 0).
Return min_effort.

Code

class Solution {
public:
    int minEffort;
    int rows, cols;
    int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited,
             int r, int c, int effort) {
        if (r == rows - 1 && c == cols - 1) {
            minEffort = min(minEffort, effort);
            return;
        }
        for (auto& d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]) {
                int newEffort = max(effort, abs(heights[r][c] - heights[nr][nc]));
                if (newEffort < minEffort) {
                    visited[nr][nc] = true;
                    dfs(heights, visited, nr, nc, newEffort);
                    visited[nr][nc] = false;
                }
            }
        }
    }

    int minimumEffortPath(vector<vector<int>>& heights) {
        rows = heights.size();
        cols = heights[0].size();
        minEffort = INT_MAX;
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        visited[0][0] = true;
        dfs(heights, visited, 0, 0, 0);
        return minEffort;
    }
};

class Solution:
    def minimumEffortPath(self, heights: list[list[int]]) -> int:
        rows, cols = len(heights), len(heights[0])
        self.min_effort = float('inf')
        visited = [[False] * cols for _ in range(rows)]

        def dfs(r: int, c: int, effort: int) -> None:
            if r == rows - 1 and c == cols - 1:
                self.min_effort = min(self.min_effort, effort)
                return
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]:
                    new_effort = max(effort, abs(heights[r][c] - heights[nr][nc]))
                    if new_effort < self.min_effort:
                        visited[nr][nc] = True
                        dfs(nr, nc, new_effort)
                        visited[nr][nc] = False

        visited[0][0] = True
        dfs(0, 0, 0)
        return self.min_effort

class Solution {
    int minEffort;
    int rows, cols;
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

    public int minimumEffortPath(int[][] heights) {
        rows = heights.length;
        cols = heights[0].length;
        minEffort = Integer.MAX_VALUE;
        boolean[][] visited = new boolean[rows][cols];
        visited[0][0] = true;
        dfs(heights, visited, 0, 0, 0);
        return minEffort;
    }

    private void dfs(int[][] heights, boolean[][] visited, int r, int c, int effort) {
        if (r == rows - 1 && c == cols - 1) {
            minEffort = Math.min(minEffort, effort);
            return;
        }
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]) {
                int newEffort = Math.max(effort, Math.abs(heights[r][c] - heights[nr][nc]));
                if (newEffort < minEffort) {
                    visited[nr][nc] = true;
                    dfs(heights, visited, nr, nc, newEffort);
                    visited[nr][nc] = false;
                }
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(4^(m × n))

In the worst case, the DFS explores all possible paths through the grid. At each cell, we have up to 4 choices (directions), and the maximum path length is m × n cells. This gives an upper bound of 4^(m × n) paths. Even with pruning, adversarial inputs can force near-exhaustive exploration.

For a 100 × 100 grid, 4^10000 is astronomically large — far beyond any time limit.

Space Complexity: O(m × n)

The recursion stack can go as deep as m × n (the longest possible path visits every cell). The visited array also takes O(m × n) space.

Why This Approach Is Not Efficient

The brute force DFS has exponential time complexity O(4^(m × n)). Even for a modest 10 × 10 grid, the number of possible paths is enormous. For the actual constraint of up to 100 × 100 grids, this approach will time out spectacularly.

The fundamental problem is that we explore the same subproblems repeatedly. When two different paths reach the same cell with different efforts, the brute force does not remember the better result — it explores all downstream paths from scratch each time.

We need a smarter strategy. One key observation: if someone told us the answer (the minimum effort value k), we could easily verify it by checking whether a path exists using only edges with height difference ≤ k. This verification is just a simple graph traversal! This insight leads to a binary search approach: search for the smallest k where such a path exists.

Better Approach - Binary Search + BFS

Intuition

Instead of finding the optimal path directly, we flip the question: "Given a maximum allowed effort k, can we reach the destination using only steps where the height difference is at most k?"

This yes/no question is easy to answer: run BFS (or DFS) from (0,0), but only traverse edges where the absolute height difference between adjacent cells is ≤ k. If the BFS reaches (rows−1, columns−1), the answer is "yes."

Now the crucial insight: the answer has a monotonic property. If we can reach the destination with effort k, we can certainly reach it with any effort k' > k (because we'd be allowing even larger steps). If we cannot reach the destination with effort k, we definitely cannot with any k' < k. This monotonicity means we can binary search on k!

The binary search range is [0, maxDiff], where maxDiff is the largest height difference between any two adjacent cells in the grid. We repeatedly halve this range:

If canReach(mid) is true → the answer is ≤ mid, so search lower.
If canReach(mid) is false → the answer is > mid, so search higher.

Think of it like a hiker choosing their maximum tolerance for steep climbs. They start with a guess, test whether a route exists within that tolerance, and adjust their guess up or down.

Step-by-Step Explanation

Let's trace with heights = [[1, 2, 2], [3, 8, 2], [5, 3, 5]]. The maximum adjacent difference is |2−8| = 6.

Binary search: low = 0, high = 6.

Step 1: mid = 3. Can we reach (2,2) using only edges with diff ≤ 3?

BFS from (0,0): Visit (0,1)[diff 1 ≤ 3 ✓], (1,0)[diff 2 ≤ 3 ✓].
From (0,1): Visit (0,2)[diff 0 ≤ 3 ✓]. Skip (1,1)[diff 6 > 3 ✗].
From (1,0): Visit (2,0)[diff 2 ≤ 3 ✓]. Skip (1,1)[diff 5 > 3 ✗].
From (0,2): Visit (1,2)[diff 0 ≤ 3 ✓].
From (1,2): Visit (2,2)[diff 3 ≤ 3 ✓]. Reached!
Result: YES. Set high = 3.

Step 2: low = 0, high = 3. mid = 1. Can we reach with diff ≤ 1?

BFS from (0,0): Visit (0,1)[diff 1 ≤ 1 ✓]. Skip (1,0)[diff 2 > 1 ✗].
From (0,1): Visit (0,2)[diff 0 ≤ 1 ✓]. Skip (1,1)[diff 6 > 1 ✗].
From (0,2): Visit (1,2)[diff 0 ≤ 1 ✓].
From (1,2): (2,2)[diff 3 > 1 ✗], (1,1)[diff 6 > 1 ✗]. Stuck!
Result: NO. Set low = 2.

Step 3: low = 2, high = 3. mid = 2. Can we reach with diff ≤ 2?

BFS from (0,0): Visit (0,1)[diff 1 ≤ 2 ✓], (1,0)[diff 2 ≤ 2 ✓].
Continue BFS: Visit (0,2), (2,0), then (1,2), (2,1).
From (2,1): Visit (2,2)[diff 2 ≤ 2 ✓]. Reached!
Result: YES. Set high = 2.

Step 4: low = 2, high = 2. Converged! Return 2.

Binary Search + BFS — Testing Effort Thresholds — Watch how binary search narrows the effort threshold while BFS checks whether the destination is reachable under each threshold. Cells blocked by high differences are avoided.

Algorithm

Compute maxDiff = maximum absolute height difference between any two adjacent cells in the grid.
Set low = 0, high = maxDiff.
While low < high:
- Set mid = (low + high) / 2.
- Run BFS/DFS from (0,0) using only edges with height difference ≤ mid.
- If BFS reaches (rows-1, columns-1): set high = mid.
- Otherwise: set low = mid + 1.
Return low.

BFS helper (canReach):

Initialize visited array. Mark (0,0) visited. Add (0,0) to queue.
While queue is not empty:
- Dequeue cell (r, c).
- If (r, c) is destination, return true.
- For each neighbor (nr, nc): if in bounds, not visited, and |heights[r][c] - heights[nr][nc]| ≤ threshold, mark visited and enqueue.
Return false.

Code

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int rows = heights.size(), cols = heights[0].size();
        int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

        int low = 0, high = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (j + 1 < cols)
                    high = max(high, abs(heights[i][j] - heights[i][j + 1]));
                if (i + 1 < rows)
                    high = max(high, abs(heights[i][j] - heights[i + 1][j]));
            }
        }

        while (low < high) {
            int mid = low + (high - low) / 2;
            // BFS to check if destination is reachable
            vector<vector<bool>> visited(rows, vector<bool>(cols, false));
            queue<pair<int, int>> q;
            q.push({0, 0});
            visited[0][0] = true;
            bool reached = false;
            while (!q.empty() && !reached) {
                auto [r, c] = q.front();
                q.pop();
                if (r == rows - 1 && c == cols - 1) {
                    reached = true;
                    break;
                }
                for (auto& d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && !visited[nr][nc]
                        && abs(heights[r][c] - heights[nr][nc]) <= mid) {
                        visited[nr][nc] = true;
                        q.push({nr, nc});
                    }
                }
            }
            if (reached) high = mid;
            else low = mid + 1;
        }

        return low;
    }
};

from collections import deque

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

        # Compute maximum adjacent difference for binary search range
        max_diff = 0
        for i in range(rows):
            for j in range(cols):
                if j + 1 < cols:
                    max_diff = max(max_diff, abs(heights[i][j] - heights[i][j + 1]))
                if i + 1 < rows:
                    max_diff = max(max_diff, abs(heights[i][j] - heights[i + 1][j]))

        def can_reach(threshold: int) -> bool:
            visited = [[False] * cols for _ in range(rows)]
            queue = deque([(0, 0)])
            visited[0][0] = True
            while queue:
                r, c = queue.popleft()
                if r == rows - 1 and c == cols - 1:
                    return True
                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < rows and 0 <= nc < cols
                            and not visited[nr][nc]
                            and abs(heights[r][c] - heights[nr][nc]) <= threshold):
                        visited[nr][nc] = True
                        queue.append((nr, nc))
            return False

        low, high = 0, max_diff
        while low < high:
            mid = (low + high) // 2
            if can_reach(mid):
                high = mid
            else:
                low = mid + 1

        return low

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length, cols = heights[0].length;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

        int low = 0, high = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (j + 1 < cols)
                    high = Math.max(high, Math.abs(heights[i][j] - heights[i][j + 1]));
                if (i + 1 < rows)
                    high = Math.max(high, Math.abs(heights[i][j] - heights[i + 1][j]));
            }
        }

        while (low < high) {
            int mid = low + (high - low) / 2;
            if (canReach(heights, rows, cols, dirs, mid))
                high = mid;
            else
                low = mid + 1;
        }

        return low;
    }

    private boolean canReach(int[][] heights, int rows, int cols,
                             int[][] dirs, int threshold) {
        boolean[][] visited = new boolean[rows][cols];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int r = cell[0], c = cell[1];
            if (r == rows - 1 && c == cols - 1) return true;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                    && !visited[nr][nc]
                    && Math.abs(heights[r][c] - heights[nr][nc]) <= threshold) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(m × n × log(maxDiff))

The binary search runs for O(log(maxDiff)) iterations, where maxDiff is the largest height difference between adjacent cells (up to 10^6, so at most ~20 iterations). Each iteration performs a BFS that visits each cell at most once, taking O(m × n) time.

Total: O(m × n × log(maxDiff)) ≈ O(20 × m × n).

For a 100 × 100 grid: ~20 × 10,000 = 200,000 operations — very fast!

Space Complexity: O(m × n)

Each BFS call uses a visited array of size m × n and a queue holding at most m × n cells.

Why This Approach Is Not Efficient

The Binary Search + BFS approach is already quite efficient at O(m × n × log(maxDiff)). However, it has two conceptual drawbacks:

Multiple full traversals: The binary search runs O(log(maxDiff)) iterations, and each iteration performs a complete BFS over the grid. Even though each BFS is O(m × n), we repeat it ~20 times.
Doesn't exploit edge weight information: BFS treats all edges equally — an edge is either traversable (diff ≤ threshold) or not. It ignores the actual magnitude of the weight. This means we cannot use the specific weight values to guide our search more efficiently.

A more elegant approach directly models this as a shortest path problem on a weighted graph. By treating each grid cell as a node and each adjacent pair as an edge weighted by their height difference, we can apply Dijkstra's algorithm — but with a twist. Instead of minimizing the SUM of edge weights, we minimize the MAXIMUM edge weight along the path.

Dijkstra's approach finds the answer in a single pass using a priority queue, rather than requiring multiple separate BFS traversals.

Optimal Approach - Modified Dijkstra's Algorithm

Intuition

We can model the grid as a weighted graph where each cell is a node and each pair of adjacent cells is connected by an edge with weight equal to their absolute height difference. The problem becomes: find the path from node (0,0) to node (rows-1, columns-1) that minimizes the maximum edge weight along the path.

This is a classic min-max path problem, which is elegantly solved by a modified version of Dijkstra's algorithm.

In standard Dijkstra, we compute the shortest distance to each node by minimizing the sum of edge weights: dist[neighbor] = dist[current] + weight. Here, we minimize the maximum edge weight: dist[neighbor] = max(dist[current], weight). The rest of the algorithm stays the same — we use a min-heap (priority queue) to always process the cell with the smallest current effort.

Why does this work? Dijkstra's correctness relies on a simple property: once we pop a node from the min-heap, we've found the optimal distance to it. This property holds for both "sum" and "max" because both operations are monotonically non-decreasing along a path. Adding more edges can only increase (or maintain) both the sum and the maximum.

Think of it as water slowly rising in the grid. The priority queue ensures we always expand to the "cheapest" neighbor first. The effort to reach a cell is like the minimum water level needed to flood a path from (0,0) to that cell. When the water reaches (rows-1, columns-1), the current water level is the answer.

Step-by-Step Explanation

Let's trace with heights = [[1, 2, 2], [3, 8, 2], [5, 3, 5]]. Initialize dist[i][j] = ∞ for all cells, except dist[0][0] = 0. Priority queue (min-heap) = [(effort=0, row=0, col=0)].

Step 1: Pop (0,0) with effort 0. Process neighbors:

(0,1): diff |1−2| = 1. New effort = max(0, 1) = 1 < ∞. Update dist[0][1] = 1. Push (1, 0, 1).
(1,0): diff |1−3| = 2. New effort = max(0, 2) = 2 < ∞. Update dist[1][0] = 2. Push (2, 1, 0).

Step 2: Pop (0,1) with effort 1. Process neighbors:

(0,2): diff |2−2| = 0. New effort = max(1, 0) = 1. Update dist[0][2] = 1. Push.
(1,1): diff |2−8| = 6. New effort = max(1, 6) = 6. Update dist[1][1] = 6. Push.
(0,0): effort max(1, 1) = 1 ≥ dist[0][0] = 0. Skip.

Step 3: Pop (0,2) with effort 1. Process:

(1,2): diff |2−2| = 0. Effort max(1, 0) = 1. Update dist[1][2] = 1. Push.

Step 4: Pop (1,2) with effort 1. Process:

(2,2): diff |2−5| = 3. Effort max(1, 3) = 3. Update dist[2][2] = 3. Push.

Step 5: Pop (1,0) with effort 2. Process:

(2,0): diff |3−5| = 2. Effort max(2, 2) = 2. Update dist[2][0] = 2. Push.
(1,1): diff |3−8| = 5. Effort max(2, 5) = 5 < 6. Update dist[1][1] = 5. Push.

Step 6: Pop (2,0) with effort 2. Process:

(2,1): diff |5−3| = 2. Effort max(2, 2) = 2. Update dist[2][1] = 2. Push.

Step 7: Pop (2,1) with effort 2. Process:

(2,2): diff |3−5| = 2. Effort max(2, 2) = 2 < 3. Update dist[2][2] = 2. Push.

Step 8: Pop (2,2) with effort 2. This is the destination! Return 2.

Modified Dijkstra — Priority Queue Relaxation on Grid — Watch how Dijkstra's algorithm uses a min-heap to always process the cell with the smallest effort first, gradually finding the minimum-effort path to the destination.

Algorithm

Initialize a 2D distance array: dist[i][j] = ∞ for all cells, dist[0][0] = 0.
Create a min-heap (priority queue) and push (effort=0, row=0, col=0).
While the heap is not empty:
- Pop (effort, r, c) with smallest effort.
- If (r, c) is the destination, return effort.
- If effort > dist[r][c], skip (stale entry).
- For each neighbor (nr, nc) in 4 directions:
  - If in bounds: compute new_effort = max(effort, |heights[r][c] - heights[nr][nc]|).
  - If new_effort < dist[nr][nc]: update dist[nr][nc] = new_effort and push to heap.
Return 0 (single-cell grid).

Code

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int rows = heights.size(), cols = heights[0].size();
        int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

        vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX));
        dist[0][0] = 0;

        // Min-heap: (effort, row, col)
        priority_queue<tuple<int,int,int>,
                       vector<tuple<int,int,int>>,
                       greater<>> pq;
        pq.push({0, 0, 0});

        while (!pq.empty()) {
            auto [effort, r, c] = pq.top();
            pq.pop();
            if (r == rows - 1 && c == cols - 1) return effort;
            if (effort > dist[r][c]) continue;
            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                    int newEffort = max(effort, abs(heights[r][c] - heights[nr][nc]));
                    if (newEffort < dist[nr][nc]) {
                        dist[nr][nc] = newEffort;
                        pq.push({newEffort, nr, nc});
                    }
                }
            }
        }

        return 0;
    }
};

import heapq

class Solution:
    def minimumEffortPath(self, heights: list[list[int]]) -> int:
        rows, cols = len(heights), len(heights[0])
        dist = [[float('inf')] * cols for _ in range(rows)]
        dist[0][0] = 0

        # Min-heap: (effort, row, col)
        heap = [(0, 0, 0)]

        while heap:
            effort, r, c = heapq.heappop(heap)
            if r == rows - 1 and c == cols - 1:
                return effort
            if effort > dist[r][c]:
                continue
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    new_effort = max(effort, abs(heights[r][c] - heights[nr][nc]))
                    if new_effort < dist[nr][nc]:
                        dist[nr][nc] = new_effort
                        heapq.heappush(heap, (new_effort, nr, nc))

        return 0

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length, cols = heights[0].length;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

        int[][] dist = new int[rows][cols];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        dist[0][0] = 0;

        // Min-heap: [effort, row, col]
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, 0, 0});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int effort = curr[0], r = curr[1], c = curr[2];
            if (r == rows - 1 && c == cols - 1) return effort;
            if (effort > dist[r][c]) continue;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                    int newEffort = Math.max(effort,
                        Math.abs(heights[r][c] - heights[nr][nc]));
                    if (newEffort < dist[nr][nc]) {
                        dist[nr][nc] = newEffort;
                        pq.offer(new int[]{newEffort, nr, nc});
                    }
                }
            }
        }

        return 0;
    }
}

Complexity Analysis

Time Complexity: O(m × n × log(m × n))

Each cell can be pushed to the priority queue multiple times (once per improvement). In the worst case, every edge triggers a push, giving O(m × n) pushes (since there are O(m × n) edges in a grid). Each heap operation (push or pop) takes O(log(m × n)) time.

Total: O(m × n × log(m × n)). For a 100 × 100 grid: 10,000 × log(10,000) ≈ 10,000 × 14 ≈ 140,000 operations — very fast.

Compared to the other approaches:

Brute Force DFS: O(4^(m×n)) — exponential, completely impractical
Binary Search + BFS: O(m × n × log(maxDiff)) — ~20 full BFS traversals
Dijkstra: O(m × n × log(m × n)) — single pass with a priority queue

Dijkstra and Binary Search + BFS have similar practical performance, but Dijkstra is more elegant and finds the answer in a single traversal.

Space Complexity: O(m × n)

The distance array uses O(m × n) space. The priority queue holds at most O(m × n) entries. Total auxiliary space is O(m × n).

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Path With Minimum Effort

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Binary Search + BFS

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Modified Dijkstra's Algorithm

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis