Swim In Rising Water - Leetcode Solution

The "Swim In Rising Water" problem on Leetcode asks us to find the minimum time required for a person to cross a grid of size n x n, where each cell in the grid represents the height of the ground. The person can move only UP, DOWN, LEFT, or RIGHT and can only move to adjacent cells with a difference of 1 in height. The water level is increasing, and the person can only move to cells that have a height less than or equal to the current water level.

We can use Dijkstra's algorithm to solve this problem. The algorithm works by maintaining a priority queue of nodes, where the priority is based on the minimum time required to reach that node. We start with the starting node and add it to the priority queue. We then process the node with the minimum time and update its neighbors accordingly.

For this problem, we can initialize the priority queue with the starting position (0, 0) and the time required to reach it, which is equal to the height of the starting position. We can use a set to keep track of the visited nodes to avoid revisiting nodes.

We then loop through the priority queue until it is empty or we have reached the end position. For each node, we check its neighbors and the time required to reach them. If the neighbor is not visited and its height is less than or equal to the current water level, we add it to the priority queue with the time required to reach it.

We update the water level as the maximum of the current water level and the height of the current node. Finally, when we reach the end position, we return the time required to reach it.

Here is the Python code to solve the "Swim In Rising Water" problem on Leetcode using Dijkstra's algorithm:

import heapq

def swimInWater(grid):
    n = len(grid)
    start = (0, 0)
    end = (n-1, n-1)
    pq = [(grid[start[0]][start[1]], start)]
    visited = set()

    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    t = 0
    while pq:
        time, pos = heapq.heappop(pq)
        visited.add(pos)

        if pos == end:
            return time

        t = max(t, grid[pos[0]][pos[1]])

        for d in directions:
            x, y = pos[0] + d[0], pos[1] + d[1]
            if 0 <= x < n and 0 <= y < n and (x, y) not in visited \
                and grid[x][y] <= t:
                heapq.heappush(pq, (grid[x][y], (x, y)))

    return -1

In the code above, we use a heapq instead of a PriorityQueue in Java, but they work in the same way. We initialize the priority queue with the starting position and the time required to reach it, which is equal to the height of the starting position. We use a set to keep track of the visited nodes.

We loop through the priority queue until it is empty or we have reached the end position. For each node, we check its neighbors and the time required to reach them. If the neighbor is not visited and its height is less than or equal to the current water level, we add it to the priority queue with the time required to reach it.

We update the water level as the maximum of the current water level and the height of the current node. Finally, when we reach the end position, we return the time required to reach it.

The time complexity of this algorithm is O(n^2 log n), where n is the size of the grid. This is because we are adding at most n^2 nodes to the priority queue, and each node takes log(n^2) time to be added or removed from the priority queue. This solution has been accepted by Leetcode.

1