Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The time needed for a path is the highest elevation along it, not the sum of its elevations. We therefore use a shortest-path search whose transition cost is a maximum: extending a route with a neighbor changes its required time to max(currentTime, neighborElevation).

Approach

Put the starting cell in a min-heap with its own elevation as the required time.
Pop the state with the smallest required time. If it is the bottom-right cell, return that time; no remaining frontier can lead to an earlier arrival.
For every in-bounds unvisited neighbor, mark it and push its coordinates with the maximum of the current time and its elevation.
Marking neighbors when enqueued is valid here: the first popped predecessor has the smallest available arrival time, and every route into the neighbor must also pay its fixed elevation. Later predecessors cannot yield a smaller maximum. A one-cell grid returns its starting elevation immediately.

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        h = [[grid[0][0], 0, 0]]
        seen = set((0, 0))

        while h:
            t, i, j = heapq.heappop(h)
            if i == n - 1 and j == n - 1:
                return t
            for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                if ni < 0 or nj < 0 or ni >= n or nj >= n or (ni, nj) in seen:
                    continue
                seen.add((ni, nj))
                heapq.heappush(h, (max(t, grid[ni][nj]), ni, nj))

Complexity analysis

For an n x n grid with N = n^2 cells, the heap processes O(N) states. Time is O(N log N) (equivalently O(n^2 log n) for n > 1) and auxiliary space is O(N); the one-cell case is constant time.