Last Day Where You Can Still Cross — DSA

Problem#

A row x col grid starts with all land cells. Each day, one cell from cells (1-indexed) floods. Return the last day on which there is a 4-connected path from any top-row land cell to any bottom-row land cell.

Examples#

row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]] → 2.
row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]] → 1.

Constraints#

2 <= row, col <= 2 * 10^4. cells.length == row * col.

Hints#

Hint 1

Going forward (flooding) is awkward; reverse time and add land each day.

Hint 2

Use two virtual nodes — top and bottom. Answer is the last day before they merge.

Approach#

Process cells in reverse order (day D down to 1). Start with everything water. On reverse day d, “add” the cell — union it with its already-added 4-neighbors. Also union top-row cells to a virtual TOP node and bottom-row cells to BOTTOM. As soon as find(TOP) == find(BOTTOM), return d - 1 (the last day before this cell was re-added, i.e., the day before the corresponding forward flooding step).

Solution#

class DSU {
public:
    vector<int> parent, rnk;
    DSU(int n) : parent(n), rnk(n, 0) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
    void unite(int a, int b) {
        a = find(a); b = find(b); if (a == b) return;
        if (rnk[a] < rnk[b]) swap(a, b);
        parent[b] = a; if (rnk[a] == rnk[b]) ++rnk[a];
    }
};

class Solution {
public:
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        int N = row * col;
        int TOP = N, BOT = N + 1;
        DSU dsu(N + 2);
        vector<vector<int>> grid(row, vector<int>(col, 0));        // 0 = water, 1 = land
        int total = cells.size();
        for (int d = total - 1; d >= 0; --d) {
            int r = cells[d][0] - 1, c = cells[d][1] - 1;
            grid[r][c] = 1;
            int u = r * col + c;
            if (r == 0)        dsu.unite(u, TOP);
            if (r == row - 1)  dsu.unite(u, BOT);
            static const int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
            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 && grid[nr][nc])
                    dsu.unite(u, nr * col + nc);
            }
            if (dsu.find(TOP) == dsu.find(BOT)) return d;
        }
        return 0;
    }
};

type dsu struct {
    parent, rnk []int
}

func newDSU(n int) *dsu {
    d := &dsu{parent: make([]int, n), rnk: make([]int, n)}
    for i := range d.parent {
        d.parent[i] = i
    }
    return d
}

func (d *dsu) find(x int) int {
    for d.parent[x] != x {
        d.parent[x] = d.parent[d.parent[x]]
        x = d.parent[x]
    }
    return x
}

func (d *dsu) unite(a, b int) {
    a, b = d.find(a), d.find(b)
    if a == b {
        return
    }
    if d.rnk[a] < d.rnk[b] {
        a, b = b, a
    }
    d.parent[b] = a
    if d.rnk[a] == d.rnk[b] {
        d.rnk[a]++
    }
}

func latestDayToCross(row, col int, cells [][]int) int {
    N := row * col
    TOP, BOT := N, N+1
    d := newDSU(N + 2)
    grid := make([][]int, row)
    for i := range grid {
        grid[i] = make([]int, col)
    }
    total := len(cells)
    dr := [4]int{-1, 1, 0, 0}
    dc := [4]int{0, 0, -1, 1}
    for day := total - 1; day >= 0; day-- {
        r, c := cells[day][0]-1, cells[day][1]-1
        grid[r][c] = 1
        u := r*col + c
        if r == 0 {
            d.unite(u, TOP)
        }
        if r == row-1 {
            d.unite(u, BOT)
        }
        for k := 0; k < 4; k++ {
            nr, nc := r+dr[k], c+dc[k]
            if nr >= 0 && nr < row && nc >= 0 && nc < col && grid[nr][nc] == 1 {
                d.unite(u, nr*col+nc)
            }
        }
        if d.find(TOP) == d.find(BOT) {
            return day
        }
    }
    return 0
}

from typing import List

class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rnk = [0] * n

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def unite(self, a: int, b: int) -> None:
        a, b = self.find(a), self.find(b)
        if a == b:
            return
        if self.rnk[a] < self.rnk[b]:
            a, b = b, a
        self.parent[b] = a
        if self.rnk[a] == self.rnk[b]:
            self.rnk[a] += 1

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        N = row * col
        TOP, BOT = N, N + 1
        dsu = DSU(N + 2)
        grid = [[0] * col for _ in range(row)]
        total = len(cells)
        dr = (-1, 1, 0, 0)
        dc = (0, 0, -1, 1)
        for day in range(total - 1, -1, -1):
            r, c = cells[day][0] - 1, cells[day][1] - 1
            grid[r][c] = 1
            u = r * col + c
            if r == 0:
                dsu.unite(u, TOP)
            if r == row - 1:
                dsu.unite(u, BOT)
            for k in range(4):
                nr, nc = r + dr[k], c + dc[k]
                if 0 <= nr < row and 0 <= nc < col and grid[nr][nc]:
                    dsu.unite(u, nr * col + nc)
            if dsu.find(TOP) == dsu.find(BOT):
                return day
        return 0

class DSU {
    constructor(n) {
        this.parent = new Array(n);
        this.rnk = new Array(n).fill(0);
        for (let i = 0; i < n; i++) this.parent[i] = i;
    }
    find(x) {
        while (this.parent[x] !== x) {
            this.parent[x] = this.parent[this.parent[x]];
            x = this.parent[x];
        }
        return x;
    }
    unite(a, b) {
        a = this.find(a); b = this.find(b);
        if (a === b) return;
        if (this.rnk[a] < this.rnk[b]) [a, b] = [b, a];
        this.parent[b] = a;
        if (this.rnk[a] === this.rnk[b]) this.rnk[a]++;
    }
}

function latestDayToCross(row, col, cells) {
    const N = row * col;
    const TOP = N, BOT = N + 1;
    const dsu = new DSU(N + 2);
    const grid = Array.from({ length: row }, () => new Array(col).fill(0));
    const total = cells.length;
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    for (let d = total - 1; d >= 0; d--) {
        const r = cells[d][0] - 1, c = cells[d][1] - 1;
        grid[r][c] = 1;
        const u = r * col + c;
        if (r === 0) dsu.unite(u, TOP);
        if (r === row - 1) dsu.unite(u, BOT);
        for (let k = 0; k < 4; k++) {
            const nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nr < row && nc >= 0 && nc < col && grid[nr][nc]) {
                dsu.unite(u, nr * col + nc);
            }
        }
        if (dsu.find(TOP) === dsu.find(BOT)) return d;
    }
    return 0;
}

class DSU {
    int[] parent, rnk;
    DSU(int n) {
        parent = new int[n];
        rnk = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (rnk[a] < rnk[b]) { int t = a; a = b; b = t; }
        parent[b] = a;
        if (rnk[a] == rnk[b]) rnk[a]++;
    }
}

class Solution {
    public int latestDayToCross(int row, int col, int[][] cells) {
        int N = row * col;
        int TOP = N, BOT = N + 1;
        DSU dsu = new DSU(N + 2);
        int[][] grid = new int[row][col];
        int total = cells.length;
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        for (int d = total - 1; d >= 0; d--) {
            int r = cells[d][0] - 1, c = cells[d][1] - 1;
            grid[r][c] = 1;
            int u = r * col + c;
            if (r == 0) dsu.unite(u, TOP);
            if (r == row - 1) dsu.unite(u, 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 && grid[nr][nc] == 1) {
                    dsu.unite(u, nr * col + nc);
                }
            }
            if (dsu.find(TOP) == dsu.find(BOT)) return d;
        }
        return 0;
    }
}

class DSU {
    private parent: number[];
    private rnk: number[];
    constructor(n: number) {
        this.parent = new Array(n);
        this.rnk = new Array(n).fill(0);
        for (let i = 0; i < n; i++) this.parent[i] = i;
    }
    find(x: number): number {
        while (this.parent[x] !== x) {
            this.parent[x] = this.parent[this.parent[x]];
            x = this.parent[x];
        }
        return x;
    }
    unite(a: number, b: number): void {
        a = this.find(a); b = this.find(b);
        if (a === b) return;
        if (this.rnk[a] < this.rnk[b]) [a, b] = [b, a];
        this.parent[b] = a;
        if (this.rnk[a] === this.rnk[b]) this.rnk[a]++;
    }
}

function latestDayToCross(row: number, col: number, cells: number[][]): number {
    const N = row * col;
    const TOP = N, BOT = N + 1;
    const dsu = new DSU(N + 2);
    const grid: number[][] = Array.from({ length: row }, () => new Array(col).fill(0));
    const total = cells.length;
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    for (let d = total - 1; d >= 0; d--) {
        const r = cells[d][0] - 1, c = cells[d][1] - 1;
        grid[r][c] = 1;
        const u = r * col + c;
        if (r === 0) dsu.unite(u, TOP);
        if (r === row - 1) dsu.unite(u, BOT);
        for (let k = 0; k < 4; k++) {
            const nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nr < row && nc >= 0 && nc < col && grid[nr][nc]) {
                dsu.unite(u, nr * col + nc);
            }
        }
        if (dsu.find(TOP) === dsu.find(BOT)) return d;
    }
    return 0;
}

Editorial#

Going forward, the grid only loses connectivity — DSU doesn’t support disunion. Reversing time turns it into an addition problem (the classic offline DSU trick). We add the latest-flooded cell first; the answer is the latest day on which top still wasn’t connected to bottom — equivalently the iteration d at which adding the cell first connects them, returned as d.

Complexity#

Time: O(R * C * α(R * C)).
Space: O(R * C).

Concept revision#

Regions Cut by Slashes