Solution: Swim in Rising Water
Tags: algorithms, javascript, java, python
Published: 2021-06-20 08:55:41

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/swim-in-rising-water/discuss/1284971).*

---

#### [Leetcode Problem #778 (*Hard*): Swim in Rising Water](https://leetcode.com/problems/swim-in-rising-water/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
On an `N x N` `grid`, each square `grid[i][j]` represents the elevation at that point `(i,j)`.
>
Now 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 distance in zero time. Of course, you must stay within the boundaries of the `grid` during your swim.
>
You start at the top left square `(0, 0)`. What is the least time until you can reach the bottom right square `(N-1, N-1)`?

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:| [[0,2],[1,3]]
Output:| 3
Explanation:|At time 0, you are in grid location (0, 0).<br><br>You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.<br><br>You cannot reach point (1, 1) until time 3.<br><br>When the depth of water is 3, we can swim anywhere inside the grid.
>
Example 2:||
|---:|---|
Input:| [[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:|We need to wait until time 16 so that (0, 0) and (4, 4) are connected.<br><br>The final route is marked in bold.
Visual:|![Example 2 Visual](https://i.imgur.com/iXBmwTd.png)

---

#### ***Constraints:***
>
 - `2 <= N <= 50`
 - `grid[i][j]` is a permutation of `[0, ..., N*N - 1]`.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

When a problem asks us to find the best path when there is something quantifiable making certain paths worse than others, one natural option would be a **Dijkstra's algorithm** approach. Dijkstra's algorithm uses a **breadth first search** (**BFS**) approach to a graph traversal, but it takes into account the weight/distance/difficulty of the different edges.

In this case, the weight will be the time required to move to a particular cell. To use Dijkstra's, we'll need to use a **min priority queue** (or **min heap**) data structure to store the possible moves at any point. These moves will be prioritized by how early they can be achieved (represented by the value in **grid[i][j]**).

Starting at **(0,0)**, we can iterate through the surrounding squares and enter them into our priority queue (**pq**). After we've entered possible cell move into **pq**, we should mark it as seen so that we don't enter the same cell into **pq** more than once.

_(**Note**: The relative values for the grid coordinates and cell values are low enough that we can optionally store all three in one integer using **bit manipulation** to lower the memory footprint of the priority queue and make it a bit more responsive.)_

We would normally create a seen matrix of **N * N** dimensions to keep track of this, but we can also use an **in-place** approach to keep this information in **grid**. To do this, we can just bump the cell value of the target cell above an arbitrarily high value. The maximum cell value will be **N * N - 1**, and since **N** caps out at **50**, we can use any value of **2500** or more for our seen marker.

After we store the new possible moves in **pq**, we then move to the next cell indicated by **pq**, remembering to keep track of the largest cell value (priority) seen so far (**ans**). We should repeat this process until we reach the end cell, and then we can **return ans**.

 - _**Time Complexity: O(N^2 * log N)** where **N** is the length of **grid**, for inserting/extracting up to **N^2** entries into the priority queue_
 - _**Space Complexity: O(N^2)** for the priority queue / heap_

---

#### ***Implementation:***

Javascript's **MinPriorityQueue()** npm is less performant than a custom heap implementation, but it is decidedly easier to use. Both are included below.

C++ defaults to a max priority queue, so we can just flip the signs on each of the insertions and extractions to convert to a min priority queue.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

***w/ MinPriorityQueue():***
```javascript
const moves = [[1,0],[0,1],[-1,0],[0,-1]]

var swimInWater = function(grid) {
    let pq = new MinPriorityQueue(),
        N = grid.length - 1, ans = grid[0][0], i = 0, j = 0
    while (i < N || j < N) {
        for (let [a,b] of moves) {
            let ia = i + a, jb = j + b
            if (ia < 0 || ia > N || jb < 0 || jb > N || grid[ia][jb] > 2500) continue
            pq.enqueue((grid[ia][jb] << 12) + (ia << 6) + jb)
            grid[ia][jb] = 3000
        }
        let next = pq.dequeue().element
        ans = Math.max(ans, next >> 12)
        i = (next >> 6) & ((1 << 6) - 1)
        j = next & ((1 << 6) - 1)
    }
    return ans
};
```

***w/ Custom Min-Heap:***
```javascript
const moves = [[1,0],[0,1],[-1,0],[0,-1]]

var swimInWater = function(grid) {
    let N = grid.length - 1, ans = grid[0][0], i = 0, j = 0, prio = 0
    
    // custom Min-Heap implementation
    let heap = [,]
    const hpush = val => {
        let i = heap.length, par = i >> 1, temp
        heap.push(val)
        while (heap[par] > heap[i]) {
            temp = heap[par], heap[par] = heap[i], heap[i] = temp
            i = par, par = i >> 1
        }
    }
    const hpop = () => {
        if (heap.length === 1) return null
        let top = heap[1], left, right, temp,
            i = 1, child = heap[3] < heap[2] ? 3 : 2
        if (heap.length > 2) heap[1] = heap.pop()
        else heap.pop()
        while (heap[i] > heap[child]) {
            temp = heap[child], heap[child] = heap[i], heap[i] = temp
            i = child, left = i << 1, right = left + 1
            child = heap[right] < heap[left] ? right : left
        }
        return top
    }
    
    while (i < N || j < N) {
        for (let [a,b] of moves) {
            let ia = i + a, jb = j + b
            if (ia < 0 || ia > N || jb < 0 || jb > N || grid[ia][jb] > 2500) continue
            hpush((grid[ia][jb] << 12) + (ia << 6) + jb)
            grid[ia][jb] = 3000
        }
        let next = hpop()
        ans = Math.max(ans, next >> 12)
        i = (next >> 6) & ((1 << 6) - 1)
        j = next & ((1 << 6) - 1)
    }
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
moves = [[1,0],[0,1],[-1,0],[0,-1]]

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        N, i, j, pq, ans = len(grid) - 1, 0, 0, [], grid[0][0]
        while i < N or j < N:
            for a,b in moves:
                ia, jb = i + a, j + b
                if ia < 0 or ia > N or jb < 0 or jb > N or grid[ia][jb] > 2500: continue
                heappush(pq, (grid[ia][jb] << 12) + (ia << 6) + jb)
                grid[ia][jb] = 3000
            nxt = heappop(pq)
            ans = max(ans, nxt >> 12)
            i = (nxt >> 6) & ((1 << 6) - 1)
            j = nxt & ((1 << 6) - 1)
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int swimInWater(int[][] grid) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int N = grid.length - 1, ans = grid[0][0], i = 0, j = 0;
        while (i < N || j < N) {
            for (int[] m : moves) {
                int ia = i + m[0], jb = j + m[1];
                if (ia < 0 || ia > N || jb < 0 || jb > N || grid[ia][jb] > 2500) continue;
                pq.add((grid[ia][jb] << 12) + (ia << 6) + jb);
                grid[ia][jb] = 3000;
            }
            int next = pq.poll();
            ans = Math.max(ans, next >> 12);
            i = (next >> 6) & ((1 << 6) - 1);
            j = next & ((1 << 6) - 1);
        }
        return ans;
    }
    private int[][] moves = {{1,0},{0,1},{-1,0},{0,-1}};
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        priority_queue<int> pq;
        int N = grid.size() - 1, ans = grid[0][0], i = 0, j = 0;
        while (i < N || j < N) {
            for (auto& m : moves) {
                int ia = i + m[0], jb = j + m[1];
                if (ia < 0 || ia > N || jb < 0 || jb > N || grid[ia][jb] > 2500) continue;
                pq.push(-(grid[ia][jb] << 12) - (ia << 6) - jb);
                grid[ia][jb] = 3000;
            }
            int next = -pq.top();
            pq.pop();
            ans = max(ans, next >> 12);
            i = (next >> 6) & ((1 << 6) - 1);
            j = next & ((1 << 6) - 1);
        }
        return ans;
    }
private:
    int moves[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
};
```