Path With Minimum Effort

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

GoogleAmazon

Problem Description

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 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.

Examples

Example 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5]] Output: 2 Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells. This is better than the route of [1,2,2,2,5], which has a maximum absolute difference of 3.

Example 2:

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

Constraints

rows == heights.length
columns == heights[i].length
1 ≤ rows, columns ≤ 100
1 ≤ heights[row][col] ≤ 10⁶

Dijkstra’s Algorithm on Grid Heights

Dijkstra’s algorithm normally finds the path that minimizes the sum of edge weights. Here, we want to find the path that minimizes the maximum edge weight along the path.

We modify Dijkstra’s path relaxation step:

Let effort[r][c] be the minimum effort to reach cell (r, c). Initialize all values to infinity, and effort[0][0] = 0.
Use a min-heap to store elements as [currentEffort, r, c], sorted by currentEffort.
Pop the element [eff, r, c] with the smallest effort. If eff > effort[r][c], skip it (we already found a better route to this cell).
If we reach the target cell (rows - 1, cols - 1), we can return its effort immediately.
For each neighbor (nr, nc), the effort to move to this neighbor is: nextEffort = max(eff, abs(heights[r][c] - heights[nr][nc]))
If nextEffort < effort[nr][nc], we update effort[nr][nc] = nextEffort and push [nextEffort, nr, nc] to the heap.

Solution: Modified Dijkstra

import java.util.*;

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

        // min-heap: [effortToCell, r, c]
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.offer(new int[]{0, 0, 0});

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

        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int eff = top[0], r = top[1], c = top[2];

            if (r == rows - 1 && c == cols - 1) return eff;
            if (eff > effort[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 diff = Math.abs(heights[r][c] - heights[nr][nc]);
                    int nextEffort = Math.max(eff, diff);

                    if (nextEffort < effort[nr][nc]) {
                        effort[nr][nc] = nextEffort;
                        heap.offer(new int[]{nextEffort, nr, nc});
                    }
                }
            }
        }

        return 0;
    }
}

import heapq

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

        # min-heap: (effort_to_cell, r, c)
        heap = [(0, 0, 0)]
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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

            if r == rows - 1 and c == cols - 1:
                return eff
            if eff > effort[r][c]:
                continue

            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    diff = abs(heights[r][c] - heights[nr][nc])
                    next_effort = max(eff, diff)

                    if next_effort < effort[nr][nc]:
                        effort[nr][nc] = next_effort
                        heapq.heappush(heap, (next_effort, nr, nc))

        return 0

#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

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

        // min-heap: {effortToCell, {r, c}}
        using T = std::pair<int, std::pair<int, int>>;
        std::priority_queue<T, std::vector<T>, std::greater<T>> heap;
        heap.push({0, {0, 0}});

        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!heap.empty()) {
            auto [eff, cell] = heap.top(); heap.pop();
            int r = cell.first, c = cell.second;

            if (r == rows - 1 && c == cols - 1) return eff;
            if (eff > effort[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 diff = std::abs(heights[r][c] - heights[nr][nc]);
                    int nextEffort = std::max(eff, diff);

                    if (nextEffort < effort[nr][nc]) {
                        effort[nr][nc] = nextEffort;
                        heap.push({nextEffort, {nr, nc}});
                    }
                }
            }
        }

        return 0;
    }
};

Complexity Analysis:

Time Complexity: O(E log V) = O(R * C * log(R * C)) where R is rows and C is columns. Each cell has at most 4 edges, and heap operations take logarithmic time.
Space Complexity: O(R * C) to store the effort grid and heap elements.