Last Day Where You Can Still Cross

hard union find grid reverse simulation

Problem

A row × col grid starts as all land. Each day one cell from the 1-based list cells floods (turns to water): on day i the cell cells[i] becomes water. Return the last day on which you can still walk from any top-row cell to any bottom-row cell, stepping only on land in the four cardinal directions.

Inputrow = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]

Output3

After day 3 the flooded cells still leave a land path from the top row to the bottom row; on day 4 they no longer do.

Inputrow = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]

Output2

After two floods a land path top-to-bottom still exists; the third flood breaks it.

row

col

cells (r:c, comma-separated, flood order)

def latestDayToCross(row, col, cells):
    n = row * col
    parent = list(range(n + 2))
    TOP, BOT = n, n + 1
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(a, b):
        parent[find(a)] = find(b)
    land = [[False] * col for _ in range(row)]
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for d in range(len(cells) - 1, -1, -1):
        r, c = cells[d][0] - 1, cells[d][1] - 1
        land[r][c] = True
        cur = r * col + c
        if r == 0: union(cur, TOP)
        if r == row - 1: union(cur, BOT)
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < row and 0 <= nc < col and land[nr][nc]:
                union(cur, nr * col + nc)
        if find(TOP) == find(BOT):
            return d
    return 0

function latestDayToCross(row, col, cells) {
  const n = row * col, TOP = n, BOT = n + 1;
  const parent = Array.from({ length: n + 2 }, (_, i) => i);
  function find(x) {
    while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
  }
  function union(a, b) { parent[find(a)] = find(b); }
  const land = Array.from({ length: row }, () => new Array(col).fill(false));
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  for (let d = cells.length - 1; d >= 0; d--) {
    const r = cells[d][0] - 1, c = cells[d][1] - 1;
    land[r][c] = true;
    const cur = r * col + c;
    if (r === 0) union(cur, TOP);
    if (r === row - 1) union(cur, BOT);
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < row && nc >= 0 && nc < col && land[nr][nc])
        union(cur, nr * col + nc);
    }
    if (find(TOP) === find(BOT)) return d;
  }
  return 0;
}

int latestDayToCross(int row, int col, int[][] cells) {
    int n = row * col, TOP = n, BOT = n + 1;
    int[] parent = new int[n + 2];
    for (int i = 0; i < n + 2; i++) parent[i] = i;
    boolean[][] land = new boolean[row][col];
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (int d = cells.length - 1; d >= 0; d--) {
        int r = cells[d][0] - 1, c = cells[d][1] - 1;
        land[r][c] = true;
        int cur = r * col + c;
        if (r == 0) union(parent, cur, TOP);
        if (r == row - 1) union(parent, cur, BOT);
        for (int[] dir : dirs) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < row && nc >= 0 && nc < col && land[nr][nc])
                union(parent, cur, nr * col + nc);
        }
        if (find(parent, TOP) == find(parent, BOT)) return d;
    }
    return 0;
}
int find(int[] p, int x) {
    while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; }
    return x;
}
void union(int[] p, int a, int b) { p[find(p, a)] = find(p, b); }

vector<int> par;
int find(int x) {
    while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; }
    return x;
}
void uni(int a, int b) { par[find(a)] = find(b); }
int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
    int n = row * col, TOP = n, BOT = n + 1;
    par.assign(n + 2, 0);
    for (int i = 0; i < n + 2; i++) par[i] = i;
    vector<vector<bool>> land(row, vector<bool>(col, false));
    int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
    for (int d = cells.size() - 1; d >= 0; d--) {
        int r = cells[d][0] - 1, c = cells[d][1] - 1;
        land[r][c] = true;
        int cur = r * col + c;
        if (r == 0) uni(cur, TOP);
        if (r == row - 1) uni(cur, BOT);
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nr < row && nc >= 0 && nc < col && land[nr][nc])
                uni(cur, nr * col + nc);
        }
        if (find(TOP) == find(BOT)) return d;
    }
    return 0;
}

Explanation

Asking for the last good day is hard to answer going forward, because removing land only ever destroys paths. The trick is to run time backwards: start from the final state where every listed cell is water, then re-add cells one at a time in reverse flood order. Adding land can only create connections, which is exactly what union-find is built for.

We model connectivity with a disjoint-set over the row · col grid cells plus two virtual nodes: TOP, joined to every land cell in row 0, and BOT, joined to every land cell in the last row. The top row can reach the bottom row exactly when find(TOP) == find(BOT).

Iterating d from the last day down to the first, we turn cells[d] back into land, union it with TOP or BOT if it sits on a border row, and union it with any of its four neighbors that are already land. The moment TOP and BOT land in the same set, the cell we just added was the one whose flooding first severed the crossing — so day d is the last day it was still possible.

Path compression (parent[x] = parent[parent[x]]) keeps find nearly constant time, so the whole sweep runs in close to linear time over the cells. The visualizer shows the grid filling back in: blue cells are re-added land, the green border bars are the virtual TOP/BOT nodes, and matching tints mark cells that share a component — watch them merge until top meets bottom.

In the default example the answer is 3: re-adding cells from day 8 down, the top and bottom components only fuse when the cell flooded on day 3 is restored, so day 3 is the last crossable day.

Time: O(row · col · α) Space: O(row · col)