Last Day Where You Can Still Cross

Intuitionturning a changing grid into one monotonic yes-or-no question

For a fixed day, the first day cells[i] are water and every later cell is still land. A crossing exists exactly when some land cell in the top row can reach some land cell in the bottom row through four-directional moves. BFS can answer that question by starting from every available top-row cell and expanding through unvisited land.

The important extra fact is that the answer changes only once. If flooding has already made crossing impossible, every later day keeps those water cells and adds more, so a path cannot reappear. The results therefore look like true, true, ..., true, false, false, ..., false, which is the shape binary search needs.

Approachbinary search the last possible day, then run BFS as the predicate

1. 1Set the binary-search range to days 0 through row x col, because day 0 has no flooded cells and after every cell is flooded no crossing can remain.
2. 2Choose the upper middle day with (lo + hi + 1) / 2, because the search asks for the greatest day that is still feasible and this avoids getting stuck when only two days remain.
3. 3Build the water grid for the first mid cells entries, because the candidate day is defined by exactly those floods and later cells must still count as land.
4. 4Start BFS from every non-water cell in the top row, marking each start visited immediately so the same cell cannot enter the queue repeatedly.
5. 5Expand to the four in-bounds neighbors that are land and unvisited, because those are precisely the legal next steps and visited cells would only duplicate work.
6. 6Return true as soon as BFS removes a cell in the bottom row, because reaching any bottom-row land cell proves that a valid crossing exists.
7. 7If BFS reaches no bottom-row cell, move hi to mid - 1; otherwise move lo to mid, because the monotonic pattern tells you which half can still contain the last feasible day.
8. 8Return lo after the range closes, because both bounds then describe the same greatest day whose crossing check returned true.

Complexitythe repeated grid checks dominate the binary search

Annotated solutionC++ · binary search with BFS feasibility checks

#include <queue>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        int n = row * col;
        int lo = 0;
        int hi = n;

        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (canCross(row, col, cells, mid)) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }

        return lo;
    }

private:
    bool canCross(int row, int col, vector<vector<int>>& cells, int day) {
        vector<vector<bool>> water(row, vector<bool>(col, false));
        for (int i = 0; i < day; ++i) {
            int r = cells[i][0] - 1;
            int c = cells[i][1] - 1;
            water[r][c] = true;
        }

        vector<vector<bool>> visited(row, vector<bool>(col, false));
        queue<pair<int, int>> q;

        for (int c = 0; c < col; ++c) {
            if (!water[0][c]) {
                q.push({0, c});
                visited[0][c] = true;
            }
        }

        int dr[4] = {-1, 1, 0, 0};
        int dc[4] = {0, 0, -1, 1};

        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop();

            if (r == row - 1) {
                return true;
            }

            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k];
                int nc = c + dc[k];

                if (nr >= 0 && nr < row && nc >= 0 && nc < col &&
                    !water[nr][nc] && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    q.push({nr, nc});
                }
            }
        }

        return false;
    }
};

The upper-middle expression is the small detail that makes this a maximum search rather than an ordinary membership search. When mid is feasible, keeping mid in the range is necessary because it might be the answer, so lo becomes mid. When it is not feasible, mid and every later day are discarded. The BFS marks a cell when it is enqueued, preventing several neighboring cells from adding it again.

Reverse flooding removes the binary searcha genuinely different approach with better asymptotic time

You can avoid rebuilding and searching many grids by reversing time. Start with every cell treated as water, then add cells back in reverse order. When cells[i] is added, the active land cells are exactly those that remain after the first i days. A disjoint-set structure joins adjacent active cells and also joins top-row cells to a virtual top node and bottom-row cells to a virtual bottom node.

#include <numeric>
#include <vector>
using namespace std;

class Solution {
    vector<int> parent;
    vector<int> size;

    int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return;
        }
        if (size[a] < size[b]) {
            swap(a, b);
        }
        parent[b] = a;
        size[a] += size[b];
    }

public:
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        int n = row * col;
        int top = n;
        int bottom = n + 1;
        parent.resize(n + 2);
        size.assign(n + 2, 1);
        iota(parent.begin(), parent.end(), 0);

        vector<vector<bool>> land(row, vector<bool>(col, false));
        int dr[4] = {-1, 1, 0, 0};
        int dc[4] = {0, 0, -1, 1};

        for (int i = n - 1; i >= 0; --i) {
            int r = cells[i][0] - 1;
            int c = cells[i][1] - 1;
            land[r][c] = true;
            int id = r * col + c;

            if (r == 0) {
                unite(id, top);
            }
            if (r == row - 1) {
                unite(id, bottom);
            }

            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (nr >= 0 && nr < row && nc >= 0 && nc < col && land[nr][nc]) {
                    unite(id, nr * col + nc);
                }
            }

            if (find(top) == find(bottom)) {
                return i;
            }
        }

        return 0;
    }
};

This reverse-time method is an optimisation, not merely a rearrangement. Each cell is activated once and each neighboring relationship is considered a constant number of times, giving O(n alpha(n)) time and O(n) extra space, where alpha is the inverse Ackermann function. The binary-search BFS version is often easier to derive and debug; the disjoint-set version is preferable when the tighter time bound matters.

Common mistakesthe wrong boundary and traversal choices are easy to miss