778. Swim In Rising Water

Problem Statement in English

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 is 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).

Approach

This is a Djikstra’s algorithm problem. We use a min-heap to always expand the least costly node first. The cost of a node is the maximum elevation we have to swim through to reach that node.

Solution in Python

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        heap = [(0, 0, 0)]

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

        while heap:
            t, x, y = heappop(heap)
            if t < grid[x][y]:
                heappush(heap, (t + 1, x, y))
                continue

            if (x, y) == (rows - 1, cols - 1):
                return t

            for dx, dy in directions:
                nx, ny = x + dx, y + dy

                if 0 <= nx < rows and 0 <= ny < cols and (nx, ny) not in seen:
                    if grid[nx][ny] <= t:
                        heappush(heap, (t, nx, ny))
                        seen.add((nx, ny))
                    else:
                        heappush(heap, (t + (grid[nx][ny] - t), x, y))

Complexity

• Time: $O((E + V) \log V)$
  Here, $E$ is the number of edges and $V$ is the number of vertices. In the worst case, we may have to explore all vertices and edges in the grid. The priority queue operations (insertion and extraction) take $O(\log V)$ time.

• Space: $O(V)$
  The space complexity is primarily determined by the storage used for the priority queue and the set of seen nodes. In the worst case, we may store all vertices in the priority queue and the seen set.

And we are done.