In this guide, you will get 778. Swim in Rising Water LeetCode Solution with the best time and space complexity. The solution to Swim in Rising Water problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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:
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.
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.
Complexity Analysis
Time Complexity: O(mn\log mn)
Space Complexity: O(mn)
778. Swim in Rising Water LeetCode Solution in C++
class Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int n = grid.size();
int ans = grid[0][0];
using T = tuple<int, int, int>; // (grid[i][j], i, j)
priority_queue<T, vector<T>, greater<>> minHeap;
vector<vector<bool>> seen(n, vector<bool>(n));
minHeap.emplace(grid[0][0], 0, 0);
seen[0][0] = true;
while (!minHeap.empty()) {
const auto [height, i, j] = minHeap.top();
minHeap.pop();
ans = max(ans, height);
if (i == n - 1 && j == n - 1)
break;
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == n || y < 0 || y == n)
continue;
if (seen[x][y])
continue;
minHeap.emplace(grid[x][y], x, y);
seen[x][y] = true;
}
}
return ans;
}
}; /* code provided by PROGIEZ */
778. Swim in Rising Water LeetCode Solution in Java
class Solution {
public int swimInWater(int[][] grid) {
final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
final int n = grid.length;
int ans = grid[0][0];
Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])) {
{ offer(new int[] {grid[0][0], 0, 0}); } // (grid[i][j], i, j)
};
boolean[][] seen = new boolean[n][n];
seen[0][0] = true;
while (!minHeap.isEmpty()) {
final int height = minHeap.peek()[0];
final int i = minHeap.peek()[1];
final int j = minHeap.poll()[2];
ans = Math.max(ans, height);
if (i == n - 1 && j == n - 1)
break;
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == n || y < 0 || y == n)
continue;
if (seen[x][y])
continue;
minHeap.offer(new int[] {grid[x][y], x, y});
seen[x][y] = true;
}
}
return ans;
}
} // code provided by PROGIEZ
778. Swim in Rising Water LeetCode Solution in Python
