300. Swim in Rising Water

The time to reach the end along a path is the maximum elevation on that path. Dijkstra with a min-heap always expands the cell reachable at the smallest such maximum, so the first time we pop the target is the answer.

Minimise the path maximum

Water level t lets you step onto any cell with elevation ≤ t. So the earliest you can traverse a path is the maximum elevation along it. We want the path whose maximum is smallest — a classic 'minimax path' solved by Dijkstra.

Min-heap by current time

Each heap entry is (time_to_here, r, c) where time_to_here is the max elevation seen on the best path to (r, c). Pop the smallest; when the target pops, that time is the answer. Pushing a neighbour uses max(time_to_here, elevation[neighbour]).

heap = [(grid[0][0], 0, 0)]
while heap:
    t, r, c = pop-min
    if (r,c) is target: return t
    for each neighbour: push (max(t, grid[nr][nc]), nr, nc)

Complexity

• Time: O(n² log n).
• Space: O(n²).

import java.util.PriorityQueue;

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        boolean[][] visited = new boolean[n][n];
        heap.offer(new int[]{grid[0][0], 0, 0});
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!heap.isEmpty()) {
            int[] cur = heap.poll();
            int t = cur[0], r = cur[1], c = cur[2];
            if (visited[r][c]) continue;
            visited[r][c] = true;
            if (r == n - 1 && c == n - 1) return t;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
                    heap.offer(new int[]{Math.max(t, grid[nr][nc]), nr, nc});
                }
            }
        }
        return -1;
    }
}