DEV Community

loading...
Cover image for Solution: Swim in Rising Water

Solution: Swim in Rising Water

seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.
・6 min read

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.


Leetcode Problem #778 (Hard): Swim in Rising Water


Description:


(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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

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:
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.

The final route is marked in bold.
Visual: Example 2 Visual

Constraints:

  • 2 <= N <= 50
  • grid[i][j] is a permutation of [0, ..., N*N - 1].

Idea:


(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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:


(Jump to: Problem Description || Solution Idea)

w/ MinPriorityQueue():

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
};
Enter fullscreen mode Exit fullscreen mode

w/ Custom Min-Heap:

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
};
Enter fullscreen mode Exit fullscreen mode

Python Code:


(Jump to: Problem Description || Solution Idea)

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
Enter fullscreen mode Exit fullscreen mode

Java Code:


(Jump to: Problem Description || Solution Idea)

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}};
}
Enter fullscreen mode Exit fullscreen mode

C++ Code:


(Jump to: Problem Description || Solution Idea)

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}};
};
Enter fullscreen mode Exit fullscreen mode

Discussion (2)

Collapse
rohithv07 profile image
Rohith V

"Dijkstra's algorithm uses a depth first search (DFS) approach to a graph traversal," - isn't it BFS. I think it is BFS instead of DFS. Correct me if I am wrong

Collapse
seanpgallivan profile image
seanpgallivan Author

You're correct. I just rushed through that description too fast and didn't notice my mistake. Fixed!