# Swim in Rising Water
**Difficulty:** HARD
[External](https://leetcode.com/problems/swim-in-rising-water)
Canonical: https://scaleengineer.com/dsa/problems/swim-in-rising-water
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Heap (Priority Queue), Matrix
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [PhonePe](https://scaleengineer.com/companies/phonepe), [WeRide](https://scaleengineer.com/companies/weride)
---
## Problem
You are given an `n x n` integer matrix `grid` where each value `grid[i][j]` represents the elevation at that point `(i, j)`.

The rain starts to fall. At time `t`, the depth of the water everywhere is `t`. 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. Of course, you must stay within the boundaries of the grid during your swim.

Return _the least time until you can reach the bottom right square_ `(n - 1, n - 1)` _if you start at the top left square_ `(0, 0)`.

**Example 1:**

![](https://assets.glich.co/dsa/swim-in-rising-water/image0.jpg) 

**Input:** grid = [[0,2],[1,3]]
**Output:** 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

**Example 2:**

![](https://assets.glich.co/dsa/swim-in-rising-water/image1.jpg) 

**Input:** 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
**Explanation:** The final route is shown.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

**Constraints:**

* `n == grid.length`
* `n == grid[i].length`
* `1 <= n <= 50`
* `0 <= grid[i][j] < n2`
* Each value `grid[i][j]` is **unique**.

# Approaches
## Binary Search on Time + BFS
The problem has a key monotonic property: if we can travel from the start to the end at a certain time `t`, we can also do so for any time `t' > t`. This allows us to binary search for the minimum required time `t`. For each guessed time `t_mid`, we solve a simpler decision problem: "Is it possible to reach the destination at time `t_mid`?". This subproblem can be solved using a standard graph traversal like BFS or DFS, where we only consider cells with elevation less than or equal to `t_mid` as valid.
**Time:** O(n^2 * log(n^2)) which simplifies to O(n^2 * log(n)). The binary search performs O(log(n^2)) iterations, and each iteration involves a BFS that takes O(n^2) time in the worst case. · **Space:** O(n^2) - For the `visited` array and the queue used in the BFS.
**Pros:** Conceptually simple and easy to implement.; Effectively reduces an optimization problem to a series of simpler decision problems.
**Cons:** It repeatedly traverses the grid, which can be less efficient than single-pass algorithms like Dijkstra's or Union-Find.; The constant factor in the time complexity might be higher compared to more direct approaches.
### Explanation
```java
class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int low = 0, high = n * n - 1;
        int ans = high;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canReach(grid, mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private boolean canReach(int[][] grid, int t) {
        int n = grid.length;
        if (grid[0][0] > t) {
            return false;
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int r = cell[0];
            int c = cell[1];

            if (r == n - 1 && c == n - 1) {
                return true;
            }

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] <= t) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        return false;
    }
}
```
### Algorithm
1. Define a search range for the answer (time `t`). The minimum possible time is `0` and the maximum is `n*n - 1`. Let `low = 0`, `high = n*n - 1`.
2. Perform a binary search on this range.
3. For each `mid` value (a potential time `t`):
    a. Check if a path exists from `(0, 0)` to `(n-1, n-1)` using only cells `(r, c)` where `grid[r][c] <= mid`.
    b. This check can be done with a standard Breadth-First Search (BFS) or Depth-First Search (DFS).
    c. The BFS starts at `(0, 0)` and explores neighbors, but only if their elevation is at most `mid`.
4. Based on the result of the path check:
    a. If a path exists, `mid` is a possible answer. We try for a better (smaller) answer by setting `high = mid - 1` and storing `mid` as the current best answer.
    b. If no path exists, `mid` is too small. We need more time, so we set `low = mid + 1`.
5. The binary search terminates when `low > high`, and the stored best answer is the minimum time required.

## Dijkstra's Algorithm / Best-First Search
This problem can be viewed as finding a path from the top-left to the bottom-right corner that minimizes the highest "cost" (elevation) of any cell along the path. This is a classic application for Dijkstra's algorithm or a Best-First Search. We use a priority queue to always explore the path that has the minimum-highest-elevation-so-far. The algorithm greedily expands paths with lower water level requirements, guaranteeing that when we first reach the destination, it will be via a path that requires the least possible time.
**Time:** O(n^2 * log(n^2)) which simplifies to O(n^2 * log(n)). Each of the `n^2` cells is added to and removed from the priority queue at most once. Each operation on the priority queue takes O(log(n^2)) time. · **Space:** O(n^2) - For the `visited` array and the priority queue, which can store up to O(n^2) elements.
**Pros:** It's a direct and elegant solution for this type of bottleneck shortest path problem.; Generally more efficient than the binary search approach as it explores the grid in a more targeted way.
**Cons:** Slightly more complex to understand and implement than a simple BFS if one is not familiar with Dijkstra's algorithm or priority queues.
### Explanation
```java
class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        // Min-heap storing {max_elevation_so_far, row, col}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        boolean[][] visited = new boolean[n][n];
        
        pq.offer(new int[]{grid[0][0], 0, 0});
        visited[0][0] = true;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!pq.isEmpty()) {
            int[] cell = pq.poll();
            int t = cell[0];
            int r = cell[1];
            int c = cell[2];

            if (r == n - 1 && c == n - 1) {
                return t;
            }

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    int newTime = Math.max(t, grid[nr][nc]);
                    pq.offer(new int[]{newTime, nr, nc});
                }
            }
        }
        return -1; // Should not be reached given the problem constraints
    }
}
```
### Algorithm
1. Model the grid as a graph where each cell is a node.
2. The problem is to find a path from `(0,0)` to `(n-1,n-1)` that minimizes the maximum elevation on the path. This is a bottleneck shortest path problem.
3. Use a priority queue (min-heap) to implement a Best-First Search, which is a variant of Dijkstra's algorithm. The priority queue will store `(time, row, col)` and will be ordered by `time`.
4. Initialize a `visited` array to keep track of visited cells.
5. Start by pushing the initial state `(grid[0][0], 0, 0)` into the priority queue.
6. While the priority queue is not empty:
    a. Pop the cell `(t, r, c)` with the minimum time `t`.
    b. If `(r, c)` is the destination, `t` is the minimum time required. Return `t`.
    c. For each unvisited neighbor `(nr, nc)` of `(r, c)`:
        i. Mark the neighbor as visited.
        ii. The time to reach this neighbor is the maximum of the current time `t` and the neighbor's elevation `grid[nr][nc]`.
        iii. Push `(max(t, grid[nr][nc]), nr, nc)` into the priority queue.

## Union-Find (Disjoint Set Union)
This approach views the problem from a connectivity perspective. We can think of the water level rising over time. As the water level `t` increases, more cells become 'swimmable'. We want to find the exact moment (the minimum `t`) when a path of swimmable cells connects the start and end points. We can simulate this process efficiently using a Union-Find (or Disjoint Set Union) data structure. We process cells in increasing order of their elevation. For each new cell that becomes swimmable, we merge its connected component with those of its already-swimmable neighbors. The answer is the elevation of the cell that causes the start and end points to be in the same component for the first time.
**Time:** O(n^2 * α(n^2)), where α is the Inverse Ackermann function. The loop runs `n^2` times, and inside, we perform a constant number of DSU operations, which have an amortized time complexity of α(n^2), a value that is nearly constant for all practical purposes. This is slightly better than O(n^2 log n). · **Space:** O(n^2) - For the DSU's parent array, the `visited` array, and the `pos` array to store coordinates.
**Pros:** Asymptotically the most efficient approach due to near-constant time DSU operations.; Provides an elegant solution by modeling the problem as a dynamic connectivity problem.
**Cons:** The most efficient implementation relies on the specific problem constraint that elevations are a permutation of `0..n^2-1`. If elevations were arbitrary, an explicit sorting step `O(n^2 log n)` would be needed, making its complexity equal to Dijkstra's.; The concept of Union-Find might be less familiar than standard graph traversals.
### Explanation
```java
class Solution {
    class DSU {
        int[] parent;
        public DSU(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        public int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }
        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
            }
        }
    }

    public int swimInWater(int[][] grid) {
        int n = grid.length;
        DSU dsu = new DSU(n * n);
        boolean[][] visited = new boolean[n][n];
        int[][] pos = new int[n * n][2];

        // Pre-compute positions of each elevation value
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                pos[grid[i][j]][0] = i;
                pos[grid[i][j]][1] = j;
            }
        }

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        // Iterate through time t = 0, 1, 2, ...
        for (int t = 0; t < n * n; t++) {
            int r = pos[t][0];
            int c = pos[t][1];
            visited[r][c] = true;
            
            // Union with visited neighbors
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && visited[nr][nc]) {
                    dsu.union(r * n + c, nr * n + nc);
                }
            }
            
            // Check if start and end are connected
            if (dsu.find(0) == dsu.find(n * n - 1)) {
                return t;
            }
        }
        
        return -1; // Should not be reached
    }
}
```
### Algorithm
1. Reframe the problem: find the earliest time `t` when `(0,0)` and `(n-1,n-1)` become connected.
2. Since cell elevations are a unique permutation of `0` to `n^2-1`, we can process cells in increasing order of their elevation, which is equivalent to processing them in increasing order of time `t`.
3. Use a helper array `pos[n*n]` where `pos[t]` stores the coordinates `(r,c)` of the cell with elevation `t`.
4. Initialize a Union-Find (DSU) data structure for `n*n` cells, where each cell is initially in its own set.
5. Iterate `t` from `0` to `n*n - 1`:
    a. Get the coordinates `(r, c)` for the cell with elevation `t` from the `pos` array.
    b. Mark this cell as 'active' (e.g., using a `visited` array).
    c. For each of its 4 neighbors, if the neighbor is already active, perform a `union` operation in the DSU between the current cell and the neighbor.
    d. After the unions, check if `(0,0)` and `(n-1,n-1)` are in the same set using the `find` operation.
    e. If they are, `t` is the first time they become connected, so it's the minimum time required. Return `t`.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
public
  int swimInWater(int[][] grid) {
    int n = grid.length;
    p = new int[n * n];
    for (int i = 0; i < p.length; ++i) {
      p[i] = i;
    }
    int[] hi = new int[n * n];
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        hi[grid[i][j]] = i * n + j;
      }
    }
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int t = 0; t < n * n; ++t) {
      int i = hi[t] / n;
      int j = hi[t] % n;
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k];
        int y = j + dirs[k + 1];
        if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] <= t) {
          p[find(x * n + y)] = find(i * n + j);
        }
        if (find(0) == find(n * n - 1)) {
          return t;
        }
      }
    }
    return -1;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  int swimInWater(vector<vector<int>> &grid) {
    int n = grid.size();
    p.resize(n * n);
    for (int i = 0; i < p.size(); ++i)
      p[i] = i;
    vector<int> hi(n * n);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        hi[grid[i][j]] = i * n + j;
    vector<int> dirs = {-1, 0, 1, 0, -1};
    for (int t = 0; t < n * n; ++t) {
      int i = hi[t] / n, j = hi[t] % n;
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] <= t)
          p[find(x * n + y)] = find(hi[t]);
        if (find(0) == find(n * n - 1))
          return t;
      }
    }
    return -1;
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
};

```

### Python

```python
class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] n = len(grid) p = list(range(n * n)) hi = [0] * (n * n) for i, row in enumerate(grid): for j, h in enumerate(row): hi[h] = i * n + j for t in range(n * n): i, j = hi[t] // n, hi[t] % n for a, b in [(0, - 1), (0, 1), (1, 0), (- 1, 0)]: x, y = i + a, j + b if 0 <= x < n and 0 <= y < n and grid[x][y] <= t: p[find(x * n + y)] = find(hi[t]) if find(0) == find(n * n - 1): return t return - 1

```