Swim in rising water
July 28, 2022
graphProblem URL: Swim in rising water
We will apply Dijkstra's greedy algorithm to solve this problem. It's basically a BFS traversal, but rather than use a regular queue, we will use a minimum heap aka. priority queue to pop from the queue. In the process we will store the maximum value of the grid's current position. After we reach the target position, that means the last position of the grid, we will return the maximum value.
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
N = len(grid)
visit = set()
minHeap = [(grid[0][0], 0, 0)]
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
visit.add((0, 0))
while minHeap:
time, r, c = heapq.heappop(minHeap)
if r == N - 1 and c == N - 1:
return time
for dr, dc in directions:
row, col = r + dr, c + dc
if (
row < 0
or col < 0
or row >= N
or col >= N
or (row, col) in visit
):
continue
visit.add((row, col))
heapq.heappush(minHeap, (max(time, grid[row][col]), row, col))
Time Complexity: O(n^2 * log(n))
, n is the number of elements in the grid.
Space Complexity: O(n)