Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Flooding only removes land, so once crossing becomes impossible it stays impossible. This monotone feasibility condition supports binary search over the day, with a graph search checking whether any dry top cell can reach the bottom.

Approach

To check day d, mark the first d listed cells as water, converting their one-based coordinates. Start BFS from all dry cells in the top row and traverse unvisited dry neighbors; reaching the bottom row makes the day feasible. Binary-search the last feasible day using an upper middle value so the feasible lower bound always advances. Day zero is all land, and after every cell floods crossing is impossible. Return the final feasible bound.

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        def solve(target):
            grid = [[0] * col for _ in range(row)]
            for i in range(target):
                r, c = cells[i]
                grid[r - 1][c - 1] = 1

            q = deque([])
            seen = set()
            for i in range(col):
                if grid[0][i] == 0:
                    q.append((0, i))
                    seen.add((0, i))

            while q:
                r, c = q.popleft()
                if r == row - 1:
                    return True
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if nr < 0 or nr >= row or nc < 0 or nc >= col or (nr, nc) in seen:
                        continue
                    if grid[nr][nc] == 0:
                        q.append((nr, nc))
                        seen.add((nr, nc))

            return False

        l = 0
        h = len(cells) - 1

        while l < h:
            mid = l + (h - l + 1) // 2
            if solve(mid):
                l = mid
            else:
                h = mid - 1

        return l

Complexity analysis

Let N = row * col. Time: O(N log N) because binary search runs an O(N) grid build and BFS at each step. Auxiliary space: O(N) for the blocked grid, visited state, and queue.