778. Swim In Rising Water - Explanation
Description
You are given a square 2-D matrix of distinct integers grid where each integer grid[i][j] represents the elevation at position (i, j).
Rain starts to fall at time = 0, which causes the water level to rise. At time t, the water level across the entire grid is t.
You may swim either horizontally or vertically in the grid between two adjacent squares if the original elevation of both squares is less than or equal to the water level at time t.
Starting from the top left square (0, 0), return the minimum amount of time it will take until it is possible to reach the bottom right square (n - 1, n - 1).
Example 1:
Input: grid = [[0,1],[2,3]]
Output: 3Explanation: For a path to exist to the bottom right square grid[1][1] the water elevation must be at least 3. At time t = 3, the water level is 3.
Example 2:
Input: grid = [
[0,1,2,10],
[9,14,4,13],
[12,3,8,15],
[11,5,7,6]
]
Output: 8Explanation: The water level must be at least 8 to reach the bottom right square. The path is [0, 1, 2, 4, 8, 7, 6].
Constraints:
grid.length == grid[i].length1 <= grid.length <= 500 <= grid[i][j] < n^2
Recommended Time & Space Complexity
You should aim for a solution with O((n^2)logn) time and O(n^2) space, where n is the number of rows or columns of the square matrix.
Hint 1
Think of this problem as a graph where each cell represents a node. You can move from one cell to its adjacent cell if the time is greater than or equal to the adjacent cell's elevation. Note that swimming does not cost time, but you may need to wait at a cell for the time to reach the required elevation. What do you notice about the path from (0, 0) to (n - 1, n - 1)? Perhaps a greedy approach would be useful here.
Hint 2
We can observe that the maximum elevation value along the path determines the time taken for that path. Therefore, we need to find the path where the maximum elevation is minimized. Can you think of an algorithm to find such a path from the source (0, 0) to the destination (n - 1, n - 1)? Perhaps a shortest path algorithm could be useful here.
Hint 3
We can use Dijkstra's algorithm. We initialize a Min-heap and a matrix with infinity. We run the algorithm starting from the source (0, 0), and we track the maximum elevation encountered along the paths. This maximum elevation is used as the key for comparison in Dijkstra's algorithm. If we encounter the destination (n - 1, n - 1), we return the maximum elevation of the path that reached the destination.
1. Brute Force
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
n = len(grid)
visit = [[False] * n for _ in range(n)]
def dfs(node, t):
r, c = node
if min(r, c) < 0 or max(r, c) >= n or visit[r][c]:
return 1000000
if r == (n - 1) and c == (n - 1):
return max(t, grid[r][c])
visit[r][c] = True
t = max(t, grid[r][c])
res = min(dfs((r + 1, c), t),
dfs((r - 1, c), t),
dfs((r, c + 1), t),
dfs((r, c - 1), t))
visit[r][c] = False
return res
return dfs((0, 0), 0)Time & Space Complexity
- Time complexity:
- Space complexity:
2. Depth First Search
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
n = len(grid)
visit = [[False] * n for _ in range(n)]
minH = maxH = grid[0][0]
for row in range(n):
maxH = max(maxH, max(grid[row]))
minH = min(minH, min(grid[row]))
def dfs(node, t):
r, c = node
if (min(r, c) < 0 or max(r, c) >= n or
visit[r][c] or grid[r][c] > t):
return False
if r == (n - 1) and c == (n - 1):
return True
visit[r][c] = True
return (dfs((r + 1, c), t) or
dfs((r - 1, c), t) or
dfs((r, c + 1), t) or
dfs((r, c - 1), t))
for t in range(minH, maxH):
if dfs((0, 0), t):
return t
for r in range(n):
for c in range(n):
visit[r][c] = False
return maxHTime & Space Complexity
- Time complexity:
- Space complexity:
3. Binary Search + DFS
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
n = len(grid)
visit = [[False] * n for _ in range(n)]
minH = maxH = grid[0][0]
for row in range(n):
maxH = max(maxH, max(grid[row]))
minH = min(minH, min(grid[row]))
def dfs(node, t):
r, c = node
if (min(r, c) < 0 or max(r, c) >= n or
visit[r][c] or grid[r][c] > t):
return False
if r == (n - 1) and c == (n - 1):
return True
visit[r][c] = True
return (dfs((r + 1, c), t) or
dfs((r - 1, c), t) or
dfs((r, c + 1), t) or
dfs((r, c - 1), t))
l, r = minH, maxH
while l < r:
m = (l + r) >> 1
if dfs((0, 0), m):
r = m
else:
l = m + 1
for row in range(n):
for col in range(n):
visit[row][col] = False
return rTime & Space Complexity
- Time complexity:
- Space complexity:
4. Dijkstra's Algorithm
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
N = len(grid)
visit = set()
minH = [[grid[0][0], 0, 0]] # (time/max-height, r, c)
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
visit.add((0, 0))
while minH:
t, r, c = heapq.heappop(minH)
if r == N - 1 and c == N - 1:
return t
for dr, dc in directions:
neiR, neiC = r + dr, c + dc
if (neiR < 0 or neiC < 0 or
neiR == N or neiC == N or
(neiR, neiC) in visit
):
continue
visit.add((neiR, neiC))
heapq.heappush(minH, [max(t, grid[neiR][neiC]), neiR, neiC])Time & Space Complexity
- Time complexity:
- Space complexity:
5. Kruskal's Algorithm
class DSU:
def __init__(self, n):
self.Parent = list(range(n + 1))
self.Size = [1] * (n + 1)
def find(self, node):
if self.Parent[node] != node:
self.Parent[node] = self.find(self.Parent[node])
return self.Parent[node]
def union(self, u, v):
pu = self.find(u)
pv = self.find(v)
if pu == pv:
return False
if self.Size[pu] < self.Size[pv]:
pu, pv = pv, pu
self.Size[pu] += self.Size[pv]
self.Parent[pv] = pu
return True
def connected(self, u, v):
return self.find(u) == self.find(v)
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
N = len(grid)
dsu = DSU(N * N)
positions = sorted((grid[r][c], r, c) for r in range(N) for c in range(N))
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for t, r, c in positions:
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < N and grid[nr][nc] <= t:
dsu.union(r * N + c, nr * N + nc)
if dsu.connected(0, N * N - 1):
return tTime & Space Complexity
- Time complexity:
- Space complexity: