Last Day Where You Can Still Cross

You are given a row x col binary matrix (1-indexed). Every day, one land cell turns into water. Given the list of cells that flood on each day, find the last day where you can still walk from the top row to the bottom row using only land cells, moving up, down, left, or right.

This is LeetCode 1970: Last Day Where You Can Still Cross. It is a hard problem that combines grid traversal with either binary search or union-find. The twist is that cells are disappearing over time, and you need to find the exact tipping point where the path breaks.

Why this problem matters

Most grid pathfinding problems give you a static grid. This one is dynamic. Cells flood one by one, and you need to find the critical moment when the last viable path from top to bottom gets cut off. That "find the threshold" framing should immediately remind you of binary search on the answer. And the "connect/disconnect components" framing should remind you of union-find.

This problem sits at the intersection of three important patterns: grid traversal, binary search on a monotonic property, and union-find for dynamic connectivity. If you are preparing for interviews at top companies, this kind of multi-pattern problem is exactly what you will face.

Two approaches

There are two clean ways to solve this.

Approach 1: Binary search + BFS. The answer has a monotonic property. If you can still cross on day d, you can definitely cross on any earlier day (fewer cells flooded). If you cannot cross on day d, you cannot cross on any later day either. So binary search on the day. For each candidate day mid, flood the first mid cells and run a BFS/DFS to check if a path still exists from any cell in the top row to any cell in the bottom row.

Approach 2: Reverse union-find. Start from the fully flooded grid (all cells are water). Then add land cells back in reverse order, day by day. Each time you add a cell, union it with its adjacent land neighbors. Maintain two virtual nodes: one representing "connected to the top row" and one representing "connected to the bottom row." The moment the top virtual node and bottom virtual node become connected, you have found your answer. This approach runs in nearly linear time and is the more elegant solution.

Let's look at the binary search + BFS approach first, since it is easier to understand. Then we will discuss why reverse union-find is faster.

Binary search + BFS solution

from collections import deque

def latest_day_to_cross(row: int, col: int, cells: list[list[int]]) -> int:
    def can_cross(day: int) -> bool:
        water = set()
        for i in range(day):
            water.add((cells[i][0] - 1, cells[i][1] - 1))

        visited = [[False] * col for _ in range(row)]
        queue = deque()

        for c in range(col):
            if (0, c) not in water:
                queue.append((0, c))
                visited[0][c] = True

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

        return False

    lo, hi = 1, len(cells)
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2
        if can_cross(mid):
            lo = mid
        else:
            hi = mid - 1

    return lo

The binary search looks for the largest day where can_cross(day) returns True. For each candidate day, we flood the first day cells, seed a BFS from every land cell in the top row, and check whether any of those BFS paths reach the bottom row.

Notice the binary search template here: we want the rightmost feasible value, so we use lo = mid when feasible and hi = mid - 1 when infeasible, with mid = lo + (hi - lo + 1) // 2 to avoid infinite loops.

Step-by-step walkthrough

Let's trace through a small example. row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]].

The grid has 4 cells and 4 days. On day 1 and day 2, a path still exists through the right column. On day 3, cell (1,2) floods and there is no way to get from row 1 to row 2 using only land. So the answer is 2.

Why reverse union-find is better

The binary search + BFS solution runs in O(row * col * log(row * col)) time. For each of the O(log(row * col)) binary search iterations, you rebuild the water set and run a BFS that takes O(row * col). It works, but it is not optimal.

The reverse union-find approach flips the problem. Instead of removing cells one at a time and checking when the path breaks, you start from the fully flooded grid and add cells back in reverse order. This turns a "when does the path break?" question into a "when does the path form?" question.

Here is the key idea:

1. Start with all cells as water
2. Create a union-find with row * col entries plus two virtual nodes: TOP and BOTTOM
3. Process cells from the last day backward to day 1
4. For each cell you restore to land, union it with any adjacent cell that is already land
5. If the restored cell is in the top row, union it with TOP. If in the bottom row, union it with BOTTOM
6. The first time find(TOP) == find(BOTTOM), the current day index is your answer

Each union and find operation is nearly O(1) with path compression and union by rank, so the total time is O(row * col * alpha(row * col)), which is effectively linear.

The reason this works is that adding cells back in reverse order is equivalent to simulating time running backward. The first time a top-to-bottom connection forms going backward corresponds to the last time that connection existed going forward.

Complexity analysis

Binary search + BFS: O(log(row * col)) iterations, each running a BFS over the grid in O(row * col). Space for the visited grid and water set is O(row * col).

Reverse union-find: Each of the row * col cells is processed once with constant-time union/find operations (amortized). The alpha function (inverse Ackermann) grows so slowly it is effectively constant. Space is O(row * col) for the union-find parent and rank arrays.

The building blocks

This problem combines several reusable pieces.

Binary search on the answer

You are not searching an array for a target. You are searching the space of possible days and using a feasibility check (BFS reachability) to decide which half to keep. This is the same pattern as Koko Eating Bananas, Capacity to Ship Packages, and Swim in Rising Water. The monotonic property (if day d works, all earlier days work too) is what makes binary search applicable.

Grid BFS for reachability

The BFS that checks whether a path exists from the top row to the bottom row is standard grid traversal. Seed the queue with all land cells in the top row, explore all four neighbors, skip water and visited cells, and return True if you reach any cell in the bottom row.

Union-find for dynamic connectivity

Union-find tracks connected components as edges (or cells) are added. The virtual node trick (connecting all top-row cells to a TOP sentinel and all bottom-row cells to a BOTTOM sentinel) reduces the connectivity check to a single find(TOP) == find(BOTTOM) query. This same pattern shows up in problems like Accounts Merge and Redundant Connection.

Reverse-time processing

When a problem asks "when does something break?", it is often easier to reverse the operations and ask "when does something form?" Removal is hard to handle with union-find, but insertion is natural. Running time backward converts removals into insertions.

Edge cases

• Single column: With col = 1, every cell that floods blocks the only column. The answer is 0 if the first cell to flood is in the only column (which it always is). Actually, with a single column you need the entire column to be land, so the answer is 0 since the very first flood blocks the path.
• Single row: row = 1. You start and end on the same row, so you need at least one land cell in that row. The answer is col - 1 (you can lose all but one cell).
• Large grids: The binary search + BFS approach may be tight on time limits. The reverse union-find approach handles large inputs comfortably.
• All cells flood: The cells list always contains row * col entries covering every cell. The answer is always at least 0 and at most row * col - 1.

From understanding to recall

You see the two approaches: binary search with a BFS feasibility check, and the more elegant reverse union-find. The concepts make sense when you read them. But can you implement the binary search loop with the correct mid calculation? Can you set up the virtual TOP and BOTTOM nodes in union-find and process cells in reverse without mixing up the indexing?

These are recall challenges, not understanding challenges. The binary search template (rightmost feasible vs. leftmost feasible) has subtle differences in how you compute mid and update lo/hi. The union-find requires remembering to check both the cell's own row (for virtual node connections) and all four neighbors (for land-to-land unions). Under interview pressure, these details slip.

Spaced repetition fixes this. You write the solution from scratch today, again in three days, again next week. After a few rounds, the reverse union-find setup and the binary search template are automatic. You see a "find the threshold day" problem and the pattern flows without hesitation.

Related posts

• Swim in Rising Water - Another grid problem combining binary search on the answer with BFS reachability
• Number of Islands - The foundational grid DFS/BFS traversal pattern used in the feasibility check
• Surrounded Regions - Grid flood fill with boundary-connected component logic

CodeBricks breaks Last Day Where You Can Still Cross into its binary-search-on-answer, grid-BFS-reachability, and reverse-union-find building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a dynamic grid connectivity problem shows up in your interview, you do not think about it. You just write it.