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 Ngrid, each squaregrid[i][j]represents the elevation at that point(i,j).Now rain starts to fall. At time
t, the depth of the water everywhere ist. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at mostt. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of thegridduring 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:
Constraints:
2 <= N <= 50grid[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
};
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
};
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
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}};
}
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}};
};
Top comments (2)
"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
You're correct. I just rushed through that description too fast and didn't notice my mistake. Fixed!