#778

Swim in Rising Water

hard· Advanced Graphsruns: 0

You are given an n x n integer matrix grid where each value represents the elevation at that point. At time t, the water level is t everywhere. You can swim from a square to another 4-directionally adjacent square only if the elevation of both squares is at most t. Starting from the top-left square (0, 0), return the minimum time until you can reach the bottom-right square (n - 1, n - 1).

wpm 0acc 100%time 0:000 / 737

import heapq

class Solution:
    def swimInWater(self, grid: list[list[int]]) -> int:
        n = len(grid)
        visited = set()
        heap = [(grid[0][0], 0, 0)]
        while heap:
            t, r, c = heapq.heappop(heap)
            if (r, c) == (n - 1, n - 1):
                return t
            if (r, c) in visited:
                continue
            visited.add((r, c))
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if (
                    0 <= nr < n
                    and 0 <= nc < n
                    and (nr, nc) not in visited
                ):
                    heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
        return -1

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.