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

If you observe closely, the answer for any given path from start to finish is the maximum elevation we encounter on the way.

So we can use a min-heap (priority queue) to always expand the least elevation node first. This way, we ensure that we are always exploring the path with the minimum possible maximum elevation.

We start from the top-left corner (0, 0) and push it into the min-heap with its elevation. We also maintain a set of seen nodes to avoid revisiting them.

This is perfect for Dijkstra’s algorithm, where we are trying to minimize the maximum elevation on the path.

Solution in Python


class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        minheap = [(grid[0][0], 0, 0)] # choke_point, i, j
        seen = set()
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        ROWS = len(grid)
        COLS = len(grid[0])

        while minheap:
            choke, i, j = heappop(minheap)

            seen.add((i, j))
            
            if i == ROWS - 1 and j == COLS - 1:
                return choke

            for dx, dy in directions:
                nx, ny = i + dx, j + dy

                if (nx, ny) in seen or not (0 <= nx < ROWS and 0 <= ny < COLS):
                    continue
                
                heappush(minheap, (max(choke, grid[nx][ny]), nx, ny))

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.