
### Problem Statement

###### 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).

![Swim in Rising Water](https://assets.leetcode.com/uploads/2021/06/29/swim2-grid-1.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._

**Steps To Solve**

- Our goal here is to reach the destination in minimum time.
- Lets take an example and understand.Say that we are only provided with two routes along the edge to move to our destination **6**. Those two routes are [0,1,2,3,4,5,16,20,6] and [0,24,12,11,10,9,8,7,6].
- Now to cross a cell we have to wait t time until the water level has risen due to rain and then only we can cross that cell.
- So now if we take the 1st route we have to wait minimum 20 time to reach our destination and if we take 2nd path we have to wait 24 time.
- Similarly we have to calculate all the routes and find the minimum time among those routes.
- Now that we have some idea about the question we see that we can use dijkstra algorithm for this problem.
- Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph.
- In the following grid lets say we have to move from (0,0) to (4,4).

  |     | 0   | 1   | 2   | 3   | 4   |
  | --- | --- | --- | --- | --- | --- |
  | 0   | 0   | 1   | 2   | 25  | 7   |
  | 1   | 22  | 26  | 27  | 28  | 8   |
  | 2   | 23  | 17  | 18  | 20  | 26  |
  | 3   | 24  | 3   | 9   | 12  | 15  |
  | 4   | 32  | 31  | 30  | 33  | 19  |

- So we start traversing from (0,0).From (0,0) we can go to (0,1)&rarr;1 and (1,0)&rarr;22 and store the values in Priority Queue.
- As 1 is less than 22 , we move to grid (0,1). From (0,1) we can move to (1,1)&rarr;26 and (0,2)&rarr;2.
- From grid(0,2) we can move to (0,3)&rarr;25 and (1,2)&rarr;27 .
- As the top element of the Priority Queue is (1,0)&rarr;22 (least value) , so now we do not move from grid (0,2) , but move to grid (1,0)&rarr;22 and mark the previous cell visited.
- From (1,0)&rarr;22 we can move to (2,0)&rarr;23 and (1,1)&rarr;26. As (2,0)&rarr;23 is the least among all , so now we are at (2,0)&rarr;23.
- From (2,0)&rarr;23 we can move to (3,0)&rarr;24 and (2,1)&rarr;17.
- As (2,1)&rarr;17 is the least among all , so now we move to (2,1)&rarr;17.
- Doing so we will reach the destination with the path where we have to wait for the minimum amount of time.
- We must ensure that we always carry the maximum value in the path along with us . For example in grid (2,0)&rarr;17 the maximum value of the path is 23 and we must store that in a variable.
- The maximum path value stored will be our mimimum time required to wait till we reach our destination.
- Lets drag us onto solution.

**JavaScript**

```js
/**
 * @param {number[][]} grid
 * @return {number}
 */
function swimInWater(grid) {
  const H = grid.length;
  const W = H && grid[0].length;
  const pq = new Heap((a, b) => grid[a[0]][a[1]] - grid[b[0]][b[1]]);
  const seen = [...Array(H)].map((r) => Array(W).fill(false));
  let max = 0;

  pq.push([0, 0]);
  seen[0][0] = true;
  while (pq.size()) {
    const [_row, _col] = pq.pop();
    max = Math.max(max, grid[_row][_col]);
    if (_row === H - 1 && _col === W - 1) {
      return max;
    }
    const dir = [
      [0, 1],
      [0, -1],
      [1, 0],
      [-1, 0],
    ];

    for (let [dirRow, dirCol] of dir) {
      const row = _row + dirRow;
      const col = _col + dirCol;
      if (row < 0 || col < 0 || row >= H || col >= W || seen[row][col])
        continue;
      seen[row][col] = true;
      pq.push([row, col]);
    }
  }
}

function Heap(compare = (a, b) => a - b) {
  const arr = [];
  return { push, pop, peek, size };

  function size() {
    return arr.length;
  }

  function push(v) {
    arr.push(v);
    bubble();
  }

  function pop() {
    const top = peek();
    const last = arr.pop();
    if (arr.length > 0) {
      arr[0] = last;
      sink();
    }
    return top;
  }

  function peek() {
    return arr[0];
  }

  function bubble() {
    let i = arr.length - 1;
    let p = (i - 1) >> 1;

    while (i !== 0 && compare(arr[i], arr[p]) < 0) {
      [arr[i], arr[p]] = [arr[p], arr[i]];
      i = p;
      p = (i - 1) >> 1;
    }
  }

  function sink() {
    let i = 0;
    for (;;) {
      let next = i;
      for (const childIdx of [i * 2 + 1, i * 2 + 2]) {
        if (childIdx < arr.length && compare(arr[childIdx], arr[next]) < 0) {
          next = childIdx;
        }
      }
      if (next === i) return;
      [arr[i], arr[next]] = [arr[next], arr[i]];
      i = next;
    }
  }
}
```

**Java** _(Dijkstra's algorithm)_

```java
class Solution {
     public int swimInWater(int[][] grid) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (grid[a[0]][a[1]] - grid[b[0]][b[1]]));
        pq.add(new int[]{0, 0});
        int level = 0;
        int n = grid.length;
        int[][] nexts = {{0 ,1}, {0, -1},{1, 0}, {-1, 0}};
        boolean[][] isVisited = new boolean[n ][n];
        while (!pq.isEmpty()){
            int[] top = pq.poll();
            level = Math.max(level, grid[top[0]][top[1]]);
            if (top[0] == n - 1 && top[1] == n - 1){
                break;
            }

            for (int[] next : nexts){
                int x = top[0] + next[0];
                int y = top[1] + next[1];
                if (!(x < 0|| x > n - 1 || y < 0 || y > n - 1)  && !isVisited[x][y]){
                    isVisited[top[0]][top[1]] = true;
                    pq.add(new int[]{x, y});
                }
            }
        }

        return level;
    }
}
```

**C++** _(Binary Search + DFS)_

```cpp
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        int low = grid[0][0], hi = n*n-1;
        while (low < hi) {
            int mid = low + (hi-low)/2;
            if (valid(grid, mid))
               hi = mid;
            else
               low = mid+1;
        }
        return low;
    }
private:
    bool valid(vector<vector<int>>& grid, int waterHeight) {
        int n = grid.size();
        vector<vector<int>> visited(n, vector<int>(n, 0));
        vector<int> dir({-1, 0, 1, 0, -1});
        return dfs(grid, visited, dir, waterHeight, 0, 0, n);
    }
    bool dfs(vector<vector<int>>& grid, vector<vector<int>>& visited, vector<int>& dir, int waterHeight, int row, int col, int n) {
        visited[row][col] = 1;
        for (int i = 0; i < 4; ++i) {
            int r = row + dir[i], c = col + dir[i+1];
            if (r >= 0 && r < n && c >= 0 && c < n && visited[r][c] == 0 && grid[r][c] <= waterHeight) {
                if (r == n-1 && c == n-1) return true;
                if (dfs(grid, visited, dir, waterHeight, r, c, n)) return true;
            }
        }
        return false;
    }
};
```

###### Time and Space Complexity

Time Complexity is **O(N&sup2;logN)**.

Space complexity in this case is **O(N&sup2;)**.
