Path With Minimum Effort

Leetcode Problem 1631: Path With Minimum Effort

Problem Summary

You are given a 2D grid of heights where each cell represents the elevation at that position. Starting from the top-left cell, you need to reach the bottom-right cell by moving up, down, left, or right. The effort of a route is defined as the maximum absolute difference in heights between any two consecutive cells along the route. Find the route that requires the minimum effort. The grid can have up to 100 rows and 100 columns, and heights range from 1 to 1,000,000.

Techniques

Array
Binary Search
Depth-First Search
Breadth-First Search
Union-Find
Heap (Priority Queue)
Matrix

Solution

import { Heap } from "../heap";

type MatrixElement = { row: number; column: number; cost: number };

function dijkstraMatrix(
    graph: number[][],
    distanceInit: number,
    newCostCondition: (currentCost: number, currentValue: number, nextValue: number) => number
): number {
    const directions = [[0, 1], [-1, 0], [0, -1], [1, 0]];
    const rows = graph.length;
    const columns = graph[0].length;
    const dist: number[][] = Array.from({ length: rows }, () => Array(columns).fill(Infinity));
    dist[0][0] = distanceInit;

    const minCostHeap = new Heap<MatrixElement>((a, b) => a.cost - b.cost);
    minCostHeap.insert({ row: 0, column: 0, cost: distanceInit });

    while (minCostHeap.size() > 0) {
        const current = minCostHeap.extract()!;
        const { row, column, cost } = current;

        if (cost > dist[row][column]) {
            continue;
        }

        for (const [dr, dc] of directions) {
            const nr = row + dr;
            const nc = column + dc;

            if (nr >= 0 && nr < rows && nc >= 0 && nc < columns) {
                const newCost = newCostCondition(cost, graph[row][column], graph[nr][nc]);

                if (newCost < dist[nr][nc]) {
                    dist[nr][nc] = newCost;
                    minCostHeap.insert({ row: nr, column: nc, cost: newCost });
                }
            }
        }
    }

    return dist[rows - 1][columns - 1];
}

function minimumEffortPath(heights: number[][]): number {
    return dijkstraMatrix(heights, 0, (currentCost, currentValue, nextValue) => Math.max(currentCost, Math.abs(currentValue - nextValue)));
};

console.log(minimumEffortPath([[1, 2, 2], [3, 8, 2], [5, 3, 5]])) // 2
console.log(minimumEffortPath([[1, 2, 3], [3, 8, 4], [5, 3, 5]])) // 1
console.log(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