Swim in Rising Water

Leetcode Problem 778: Swim in Rising Water

Problem Summary

You are given an n x n grid where each cell contains a unique elevation value. Water rises over time: at time t, any cell with elevation at most t is reachable. You can swim from one cell to any 4-directionally adjacent cell if both cells have elevation at most t. Swimming takes zero time and covers infinite distance. Starting from the top-left cell, find the minimum time until you can reach the bottom-right cell. The grid size can be up to 50 x 50, and elevation values range from 0 to n^2 - 1, with each value appearing exactly once.

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 swimInWater(grid: number[][]): number {
    return dijkstraMatrix(grid, grid[0][0], (currentCost, _, nextValue) => Math.max(currentCost, nextValue));
};

console.log(swimInWater([[0, 2], [1, 3]])) // 3
console.log(swimInWater([[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]])) // 16