Swim in Rising Water

Swim in Rising Water hard

Description

You are given an n × n integer matrix grid where each value grid[i][j] represents the elevation at that point.

Rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a cell to a 4-directionally adjacent cell if and only if the elevations of both cells are at most t. You can swim infinitely fast in zero time.

Starting at the top-left cell (0, 0), return the least time until you can reach the bottom-right cell (n-1, n-1).

Examples

> Case 1:
    grid = [[0,2],[1,3]]
    Output: 3
    # At t=3 all four cells are passable. (0,0) → (1,0) → (1,1).
 
> Case 2:
    grid = [[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]]
    Output: 16

Constraints

n == grid.length == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n²
Each value in grid is unique.

State design

The answer is the smallest t such that there’s a path from (0,0) to (n-1,n-1) using only cells with value ≤ t.

That’s max(grid[cell] along the path) for some path — and we want to minimize that max. Classic minimax shortest path.

Same trick as Path with Minimum Effort: Dijkstra, but the path cost is the max cell value along the path (instead of the sum). Relaxation becomes:

new_time = max(time_so_far, grid[neighbor])

Code

Alternative — Union Find

There’s a beautiful alternative: process cells in increasing order of elevation, unioning each with its already-processed neighbors. The answer is the value of the cell whose insertion first connects (0,0) to (n-1,n-1). Worth knowing as a cross-reference to Day 20 — Union Find.

Analysis

Time: O(n² · log n) — Dijkstra on n² vertices.
Space: O(n²).

The minimax-Dijkstra trick (replace sum with max) and the Union-Find approach (process cells by sorted weight) are two ways of saying the same thing — both are computing the bottleneck-minimum spanning path, which corresponds to a path in the minimum spanning tree. The minimax path in any weighted graph is a path in the MST.

Same skin

Path with Minimum Effort — same skeleton, abs(height_diff) instead of grid[cell].
Path With Maximum Minimum Value — flip min and max.
Cheapest Move on a Grid — sum-based grid Dijkstra.

Word Ladder The Maze II