778. Swim in Rising Water

In an n×n grid of distinct elevations, the water level at time t is t. You can swim between 4-adjacent cells if both elevations are ≤ t. Return the least time at which you can reach (n−1, n−1) from (0, 0).

The cost of a path is its highest elevation. Expand cells from a min-heap keyed by that cost; the first time the corner is popped, its cost is the answer.

1function swimInWater(grid: number[][]): number {
2  const n = grid.length, seen = new Set<number>([0]);
3  const heap = new MinPriorityQueue<[number, number, number]>((e) => e[0]);
4  heap.enqueue([grid[0][0], 0, 0]);
5  while (true) {
6    const [t, r, c] = heap.dequeue();
7    if (r === n - 1 && c === n - 1) return t;
8    for (const [x, y] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]])
9      if (x >= 0 && y >= 0 && x < n && y < n && !seen.has(x * n + y)) {
10        seen.add(x * n + y); heap.enqueue([Math.max(t, grid[x][y]), x, y]);
11      }
12  }
13}

elevation

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

min-heap (time @ cell)

0 @ (0,0)

Start at (0, 0) with time 0.

1 / 0

Space: play/pause · ←/→: step