The Question
Coding

Swim in Rising Water

You are given an $n \times n$ integer matrix grid where each value grid[i][j] represents the elevation at that point $(i, j)$. It starts raining, and water gradually rises over time. At time $t$, the water level is $t$, meaning any cell with elevation less than or equal to $t$ is submerged and can be swam through. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most $t$. You can swim infinite distances in zero time. You must stay within the boundaries of the grid. Return the minimum time $t$ required to reach the bottom-right square $(n - 1, n - 1)$ starting from the top-left square $(0, 0)$. ### Constraints - $n == \text{grid.length} == \text{grid[i].length}$ - $1 \le n \le 50$ - $0 \le \text{grid}[i][j] < n^2$ - Each value in grid is unique.
Java
Dijkstra's Algorithm
Priority Queue
Disjoint Set Union
Questions & Insights

Clarifying Questions

What are the constraints on $n$ (the grid size) and the values inside `grid[i][j]`?
Assumption: n is between 1 and 50. The grid values are a permutation of integers from 0 to n^2 - 1 (or generally non-negative integers).
Can we start with a grid of size $1 \times 1$?
Assumption: Yes, if the grid is 1 \times 1, the minimum time required should simply be the value of grid[0][0].
Are we allowed to move diagonally, or only 4-directionally (up, down, left, right)?
Assumption: Only 4-directionally as stated ("4-directionally adjacent square").
What are the time and space complexity expectations?
Assumption: An O(n^2 \log n) time complexity and O(n^2) space complexity solution is highly optimal and fully acceptable.

Thinking Process

Identify the Core Problem: This is a classic minimax path problem on a grid. We want to find a path from (0, 0) to (n - 1, n - 1) such that the maximum elevation (water level t) encountered along the path is minimized.
Formulate the Algorithm:
We can adapt Dijkstra's Algorithm. Instead of minimizing the sum of edge weights, we minimize the maximum node value along the path.
Let d[r][c] be the minimum time required to reach cell (r, c).
We start at (0, 0) with an initial cost of grid[0][0].
A min-heap (Priority Queue) will store the cells ordered by the minimum-maximum elevation required to reach them.
Trace the Transitions:
When we transition from cell u to an adjacent cell v, the cost to reach via u is \max(\text{cost}(u), \text{grid}[v]).
We greedily expand the cell with the smallest path cost first. The first time we reach (n-1, n-1), we are guaranteed to have found the optimal minimum time.
Implementation Breakdown

Problem Set

Functional Requirements:
Input: An n \times n 2D integer array grid.
Output: An integer representing the minimum time to reach (n - 1, n - 1) from (0, 0).
Constraints:
n = \text{grid.length} = \text{grid[i].length}
1 \le n \le 50
0 \le \text{grid}[i][j] < n^2
Each value in grid is unique.

Approach

Algorithm: Modified Dijkstra's Algorithm (Minimax path).
Data Structure: Priority Queue (Min-Heap) and a 2D boolean array to track visited cells.
Complexity:
Time Complexity: O(n^2 \log n) because there are n^2 states (cells), and each cell is pushed and popped from the Priority Queue at most once. Each heap operation takes O(\log(n^2)) = O(\log n) time.
Space Complexity: O(n^2) to store the visited states and the Priority Queue elements.

Implementation

Wrap Up

Advanced Topics

Binary Search on Answer + BFS/DFS:
An alternative approach is to perform a binary search on the time t in the range [0, n^2 - 1]. For each candidate t, run a standard DFS or BFS to see if a valid path exists from start to end using only cells with elevation \le t.
Time Complexity: O(n^2 \log(n^2)) = O(n^2 \log n), which is asymptotically the same as Dijkstra's but often has different constant factors. It can be easier to parallelize because each check is independent.
Union-Find (Disjoint Set Union):
We can sort all cell coordinates by their elevation values. Starting with an empty grid, we gradually "activate" cells in increasing order of elevation and union adjacent active cells. The algorithm terminates when (0, 0) and (n-1, n-1) belong to the same connected component.
Time Complexity: O(n^2 \log n) due to sorting. The Union-Find operations take O(n^2 \alpha(n^2)) where \alpha is the Inverse Ackermann function, making this approach highly competitive in practice.