Swim in Rising Water

main.md

Question

Approach

I approach this problem by treating the grid as a graph where each cell represents a node, and I aim to find a path from the top-left to the bottom-right that minimizes the highest elevation encountered along the way. Since water rises over time, the minimum time required to reach the destination equals the smallest possible “maximum elevation” on any valid path. To achieve this, I use a min-heap (priority queue) similar to Dijkstra’s algorithm, always exploring the cell with the lowest elevation first while keeping track of the maximum elevation seen so far. Once I reach the bottom-right cell, that maximum elevation represents the minimum time needed to swim across.

Implementation

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        visited = set()
        heap = [(grid[0][0], 0, 0)]
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        res = 0

        while heap:
            t, r, c = heapq.heappop(heap)
            res = max(res, t)
            if (r, c) == (n - 1, n - 1):
                return res
            if (r, c) in visited:
                continue
            visited.add((r, c))

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
                    heapq.heappush(heap, (grid[nr][nc], nr, nc))

Complexities

• Time: O(n^2 logn)
• Space: O(n ^ 2)