LeetCode 1970 - Last Day Where You Can Still Cross

This problem asks us to find the last day we can cross a grid from the top row to the bottom row, walking only on land. The grid is initially all land (0), and each day, specific cells are flooded with water (1) according to the cells array.

leetcodehardarraybinary-searchdepth-first-searchbreadth-first-searchunion-findmatrix

LeetCode Problem 1970

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Solution

Problem Understanding

This problem asks us to find the last day we can cross a grid from the top row to the bottom row, walking only on land. The grid is initially all land (0), and each day, specific cells are flooded with water (1) according to the cells array. Each entry cells[i] = [ri, ci] tells us that on day i + 1 (1-based), the cell at row ri and column ci becomes water.

The input consists of row and col defining the grid size, and a cells list that will flood every cell over time. The output is the last day (1-based) where it is still possible to traverse from any top row cell to any bottom row cell using only land cells and moving in four directions (up, down, left, right).

Constraints reveal that the matrix can be up to 2 * 10^4 cells in total, and all cells values are unique. This implies that any naive approach checking each day linearly with full traversals would be inefficient. The problem guarantees that each cell is flooded exactly once, so we do not need to handle repeated flooding events.

Important edge cases include a very narrow grid (like 2xN), a grid where flooding occurs in a single column or row first, or situations where the last top-to-bottom path is blocked late in the sequence.

Approaches

Brute Force

A brute-force approach would simulate the flooding day by day. On each day, we would mark the corresponding cell as water and then perform a search from the top row to see if any path to the bottom row exists. This search could be BFS or DFS. We would continue until no path exists and return the last day when a path was possible.

While correct, this approach is too slow because performing BFS/DFS on a grid of size row * col for potentially every day (up to row * col days) would result in O((row * col)^2) time complexity, which is infeasible for large grids.

Optimal Approach

The key observation is that the problem is monotonic: once a path is blocked on a certain day, all subsequent days will also be blocked. This allows us to use binary search over the day number, combined with BFS or DFS to check connectivity for a given day.

We can define a helper function canCross(day) that builds the grid after flooding all cells up to that day, then checks if a top-to-bottom path exists. Binary search over the day range [1, len(cells)] allows us to find the last day efficiently.

Union-Find is another alternative to BFS for connectivity checks, but BFS/DFS is simpler to implement and understand for this problem.

Approach Time Complexity Space Complexity Notes
Brute Force O((row * col)^2) O(row * col) Flood day by day, BFS/DFS to check path
Binary Search + BFS O(row * col * log(row * col)) O(row * col) Binary search over days with BFS to check paths

Algorithm Walkthrough

  1. Binary Search Setup: Initialize left = 1 and right = row * col. We will search for the last day where crossing is possible.
  2. Flood Grid Function: For a given day d, create a grid where the first d cells from cells are water and the rest are land.
  3. Path Check Function: Use BFS or DFS starting from all land cells in the top row. Traverse only land cells. If any cell in the bottom row is reached, return True.
  4. Binary Search Iteration: While left <= right, compute mid = (left + right) // 2. Use canCross(mid) to check if crossing is possible on that day.
  5. Update Search Range: If canCross(mid) is True, move left to mid + 1 (we can try later days). If False, move right to mid - 1 (crossing not possible, try earlier day).
  6. Return Result: After the binary search completes, right will be the last day crossing is possible.

Why it works: The invariant is that crossing is possible for all days <= last possible day and impossible for days > last day. Binary search efficiently finds the transition point.

Python Solution

from collections import deque
from typing import List

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        def canCross(day: int) -> bool:
            grid = [[0] * col for _ in range(row)]
            for i in range(day):
                r, c = cells[i]
                grid[r-1][c-1] = 1
            
            queue = deque()
            for c in range(col):
                if grid[0][c] == 0:
                    queue.append((0, c))
                    grid[0][c] = 1  # mark visited

            directions = [(0,1),(1,0),(0,-1),(-1,0)]
            while queue:
                r, c = queue.popleft()
                if r == row - 1:
                    return True
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < row and 0 <= nc < col and grid[nr][nc] == 0:
                        grid[nr][nc] = 1
                        queue.append((nr, nc))
            return False

        left, right = 1, row * col
        last_day = 0
        while left <= right:
            mid = (left + right) // 2
            if canCross(mid):
                last_day = mid
                left = mid + 1
            else:
                right = mid - 1
        return last_day

Explanation: We first define canCross(day) to simulate the grid after day floods and perform BFS from the top row. During BFS, visited land cells are marked as water to avoid revisiting. Binary search then efficiently finds the last day where a path exists.

Go Solution

package main

func latestDayToCross(row int, col int, cells [][]int) int {
    canCross := func(day int) bool {
        grid := make([][]int, row)
        for i := range grid {
            grid[i] = make([]int, col)
        }
        for i := 0; i < day; i++ {
            r, c := cells[i][0]-1, cells[i][1]-1
            grid[r][c] = 1
        }

        type point struct{ r, c int }
        queue := []point{}
        for c := 0; c < col; c++ {
            if grid[0][c] == 0 {
                queue = append(queue, point{0, c})
                grid[0][c] = 1
            }
        }

        directions := []point{{0,1},{1,0},{0,-1},{-1,0}}
        for len(queue) > 0 {
            p := queue[0]
            queue = queue[1:]
            if p.r == row-1 {
                return true
            }
            for _, d := range directions {
                nr, nc := p.r + d.r, p.c + d.c
                if nr >= 0 && nr < row && nc >= 0 && nc < col && grid[nr][nc] == 0 {
                    grid[nr][nc] = 1
                    queue = append(queue, point{nr, nc})
                }
            }
        }
        return false
    }

    left, right := 1, row * col
    lastDay := 0
    for left <= right {
        mid := (left + right) / 2
        if canCross(mid) {
            lastDay = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return lastDay
}

Go-specific notes: We use slices to represent the grid and a slice-based queue for BFS. The point struct helps manage coordinates. The logic mirrors the Python implementation, handling 0-based indexing carefully for the grid.

Worked Examples

Example 1: row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]

Day Flooded Cells BFS Path Exists?
1 [1,1] Yes (1,2 → 2,2)
2 [1,1],[2,1] Yes (1,2 → 2,2)
3 [1,1],[2,1],[1,2] No
4 All No

Last day = 2.

Example 2: row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]

Day Flooded Cells BFS Path Exists?
1 [1,1] Yes (1,2 → 2,2)
2 [1,1],[1,2]