778. Swim in Rising Water
Problem Description
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).
Examples:
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.
Example 2:
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 marked. 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] < n^2
- Each value grid[i][j] is unique
Python Solution
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
n = len(grid)
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def can_swim(t):
visited = set()
def dfs(x, y):
if x == n-1 and y == n-1:
return True
visited.add((x, y))
for dx, dy in directions:
new_x, new_y = x + dx, y + dy
if (0 <= new_x < n and 0 <= new_y < n and
(new_x, new_y) not in visited and
grid[new_x][new_y] <= t):
if dfs(new_x, new_y):
return True
return False
return dfs(0, 0)
# Binary search for minimum time
left, right = grid[0][0], n * n - 1
while left < right:
mid = (left + right) // 2
if can_swim(mid):
right = mid
else:
left = mid + 1
return leftImplementation Notes:
- Uses binary search to find minimum time
- DFS to check if path exists at given time
- Time complexity: O(n^2 log n)
- Space complexity: O(n^2) for visited set
Java Solution
class Solution {
private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public int swimInWater(int[][] grid) {
int n = grid.length;
// Binary search for minimum time
int left = grid[0][0];
int right = n * n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (canSwim(grid, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canSwim(int[][] grid, int t) {
int n = grid.length;
boolean[][] visited = new boolean[n][n];
return dfs(grid, visited, 0, 0, t);
}
private boolean dfs(int[][] grid, boolean[][] visited, int x, int y, int t) {
int n = grid.length;
if (x == n - 1 && y == n - 1) {
return true;
}
visited[x][y] = true;
for (int[] dir : DIRECTIONS) {
int newX = x + dir[0];
int newY = y + dir[1];
if (newX >= 0 && newX < n && newY >= 0 && newY < n &&
!visited[newX][newY] && grid[newX][newY] <= t) {
if (dfs(grid, visited, newX, newY, t)) {
return true;
}
}
}
return false;
}
}C++ Solution
class Solution {
private:
const vector> DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool canSwim(const vector>& grid, int t) {
int n = grid.size();
vector> visited(n, vector(n, false));
return dfs(grid, visited, 0, 0, t);
}
bool dfs(const vector>& grid, vector>& visited,
int x, int y, int t) {
int n = grid.size();
if (x == n - 1 && y == n - 1) {
return true;
}
visited[x][y] = true;
for (const auto& dir : DIRECTIONS) {
int newX = x + dir[0];
int newY = y + dir[1];
if (newX >= 0 && newX < n && newY >= 0 && newY < n &&
!visited[newX][newY] && grid[newX][newY] <= t) {
if (dfs(grid, visited, newX, newY, t)) {
return true;
}
}
}
return false;
}
public:
int swimInWater(vector>& grid) {
int n = grid.size();
// Binary search for minimum time
int left = grid[0][0];
int right = n * n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (canSwim(grid, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}; JavaScript Solution
function swimInWater(grid) {
const DIRECTIONS = [[0, 1], [1, 0], [0, -1], [-1, 0]];
const n = grid.length;
function canSwim(t) {
const visited = Array(n).fill().map(() => Array(n).fill(false));
function dfs(x, y) {
if (x === n - 1 && y === n - 1) {
return true;
}
visited[x][y] = true;
for (const [dx, dy] of DIRECTIONS) {
const newX = x + dx;
const newY = y + dy;
if (newX >= 0 && newX < n && newY >= 0 && newY < n &&
!visited[newX][newY] && grid[newX][newY] <= t) {
if (dfs(newX, newY)) {
return true;
}
}
}
return false;
}
return dfs(0, 0);
}
// Binary search for minimum time
let left = grid[0][0];
let right = n * n - 1;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (canSwim(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}C# Solution
public class Solution {
private static readonly int[][] DIRECTIONS = new int[][] {
new int[] { 0, 1 },
new int[] { 1, 0 },
new int[] { 0, -1 },
new int[] { -1, 0 }
};
public int SwimInWater(int[][] grid) {
int n = grid.Length;
// Binary search for minimum time
int left = grid[0][0];
int right = n * n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (CanSwim(grid, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private bool CanSwim(int[][] grid, int t) {
int n = grid.Length;
bool[,] visited = new bool[n, n];
return Dfs(grid, visited, 0, 0, t);
}
private bool Dfs(int[][] grid, bool[,] visited, int x, int y, int t) {
int n = grid.Length;
if (x == n - 1 && y == n - 1) {
return true;
}
visited[x, y] = true;
foreach (var dir in DIRECTIONS) {
int newX = x + dir[0];
int newY = y + dir[1];
if (newX >= 0 && newX < n && newY >= 0 && newY < n &&
!visited[newX, newY] && grid[newX][newY] <= t) {
if (Dfs(grid, visited, newX, newY, t)) {
return true;
}
}
}
return false;
}
}Implementation Notes:
- Uses binary search to find minimum time
- DFS to check if path exists at given time
- Time complexity: O(n^2 log n)
- Space complexity: O(n^2) for visited array