# Last Day Where You Can Still Cross
**Difficulty:** HARD
[External](https://leetcode.com/problems/last-day-where-you-can-still-cross)
Canonical: https://scaleengineer.com/dsa/problems/last-day-where-you-can-still-cross
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Matrix
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian)
---
## Problem
There is a **1-based** binary matrix where `0` represents land and `1` represents water. You are given integers `row` and `col` representing the number of rows and columns in the matrix, respectively.

Initially on day `0`, the **entire** matrix is **land**. However, each day a new cell becomes flooded with **water**. You are given a **1-based** 2D array `cells`, where `cells[i] = [ri, ci]` represents that on the `ith` day, the cell on the `rith` row and `cith` column (**1-based** coordinates) will be covered with **water** (i.e., changed to `1`).

You want to find the **last** day that it is possible to walk from the **top** to the **bottom** by only walking on land cells. You can start from **any** cell in the top row and end at **any** cell in the bottom row. You can only travel in the **four** cardinal directions (left, right, up, and down).

Return _the **last** day where it is possible to walk from the **top** to the **bottom** by only walking on land cells_.

**Example 1:**

![](https://assets.glich.co/dsa/last-day-where-you-can-still-cross/image0.png) 

**Input:** row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
**Output:** 2
**Explanation:** The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 2.

**Example 2:**

![](https://assets.glich.co/dsa/last-day-where-you-can-still-cross/image1.png) 

**Input:** row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
**Output:** 1
**Explanation:** The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 1.

**Example 3:**

![](https://assets.glich.co/dsa/last-day-where-you-can-still-cross/image2.png) 

**Input:** row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
**Output:** 3
**Explanation:** The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 3.

**Constraints:**

* `2 <= row, col <= 2 * 104`
* `4 <= row * col <= 2 * 104`
* `cells.length == row * col`
* `1 <= ri <= row`
* `1 <= ci <= col`
* All the values of `cells` are **unique**.

# Approaches
## Linear Scan with Graph Traversal
This approach simulates the process chronologically, day by day. For each day, it constructs the grid with the corresponding water cells and then performs a full graph traversal (like Breadth-First Search or Depth-First Search) to determine if a path from the top row to the bottom row still exists on land. It continues this process until it finds the first day where a path is no longer possible.
**Time:** O(k * (row * col)), where `k` is the final answer. In the worst case, `k` can be close to `row * col`, leading to a complexity of O((row * col)^2). Each path check involves building a grid (O(k)) and running a BFS (O(row * col)). · **Space:** O(row * col) to store the grid, the BFS queue, and a visited set. In the provided code snippet, the grid itself is used to mark visited cells, but the space complexity remains the same.
**Pros:** Straightforward and easy to conceptualize, as it directly models the problem statement.
**Cons:** Highly inefficient due to repeated computations.; The time complexity is quadratic in the number of cells, which will be too slow for the given constraints and likely result in a 'Time Limit Exceeded' error.
### Explanation
We iterate through the days, starting from day 1. In each iteration `d`, we first set up the `row x col` grid. We mark all cells as land, then iterate from `k = 0` to `d-1`, marking each `cells[k]` as water. After setting up the grid for day `d`, we check for a path. A common way to do this is with Breadth-First Search (BFS). We can start a BFS from all land cells in the top row simultaneously. The BFS explores adjacent land cells level by level. If the search ever reaches any cell in the bottom row, we know a path exists for day `d`. We store this day `d` as our current best answer and proceed to the next day. The first day we find that no path exists, we can stop, and the answer is the last successful day we recorded.

```java
class Solution {
    public int lastDayToCross(int row, int col, int[][] cells) {
        int ans = 0;
        for (int d = 1; d <= cells.length; d++) {
            if (canCrossOnDay(row, col, cells, d)) {
                ans = d;
            } else {
                break;
            }
        }
        return ans;
    }

    private boolean canCrossOnDay(int row, int col, int[][] cells, int day) {
        int[][] grid = new int[row][col];
        for (int i = 0; i < day; i++) {
            grid[cells[i][0] - 1][cells[i][1] - 1] = 1; // Mark as water
        }

        java.util.Queue<int[]> queue = new java.util.LinkedList<>();
        for (int c = 0; c < col; c++) {
            if (grid[0][c] == 0) {
                queue.offer(new int[]{0, c});
                grid[0][c] = -1; // Mark as visited
            }
        }

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

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0];
            int c = curr[1];

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

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

                if (nr >= 0 && nr < row && nc >= 0 && nc < col && grid[nr][nc] == 0) {
                    grid[nr][nc] = -1; // Mark as visited
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        return false;
    }
}
```
### Algorithm
*   Initialize `ans = 0`.
*   Loop through each day `d` from `1` to `row * col`.
*   For each day `d`, create a grid representing the state of land and water. This involves marking cells `cells[0]` through `cells[d-1]` as water.
*   Call a helper function, `pathExists(grid)`, to check if there's a path from any cell in the top row to any cell in the bottom row.
*   If `pathExists(grid)` returns `true`, it means it's possible to cross on day `d`, so we update our potential answer: `ans = d`.
*   If `pathExists(grid)` returns `false`, it means from this day onwards, it's impossible to cross. We can break the loop as any subsequent day will also not have a path.
*   Return `ans`.

**`pathExists(grid)` function using BFS:**
*   Initialize a queue and a `visited` 2D array.
*   Add all land cells in the top row (row 0) to the queue and mark them as visited.
*   While the queue is not empty:
    *   Dequeue a cell `(r, c)`.
    *   If this cell is in the bottom row (`r == row - 1`), a path has been found, so return `true`.
    *   Explore its four neighbors `(nr, nc)`.
    *   If a neighbor is within the grid boundaries, is a land cell, and has not been visited, enqueue it and mark it as visited.
*   If the queue becomes empty and the bottom row was not reached, it means no path exists. Return `false`.

## Binary Search on the Day
A key observation is that the problem has a monotonic property: if you can cross the grid on day `d`, you can certainly cross it on any day before `d` (since there would be less water). This property makes the problem a perfect candidate for binary search. We can binary search on the day number. For any given day `mid`, we can efficiently check if a path exists by building the grid for that day and running a single BFS/DFS.
**Time:** O(row * col * log(row * col)). The binary search performs `log(row * col)` calls to `canCrossOnDay`. Each call takes O(row * col) time to build the grid and run the BFS. · **Space:** O(row * col). This space is used within the `canCrossOnDay` function to store the grid, the BFS queue, and visited information.
**Pros:** Much more efficient than the linear scan, with a logarithmic factor instead of a linear one.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** While much faster than a linear scan, it's not the most optimal solution.; It repeatedly builds the grid from scratch for each check, which involves redundant computations.
### Explanation
Instead of checking each day one by one, we can significantly speed up the search for the correct day. The range of possible answers is from day 0 to day `row * col`. We can apply binary search on this range.

For each `mid` day we test, we need a function `canCross(day)` to tell us if a path exists. This function works as follows:
1.  Create a `row x col` grid.
2.  Flood the cells that become water by day `mid`. These are `cells[0]` through `cells[mid-1]`.
3.  Use BFS (or DFS) to check for a path from the top row to the bottom row on the remaining land cells.

If `canCross(mid)` is true, we know that day `mid` is possible, so the answer could be `mid` or a later day. We update our answer and search in the range `[mid + 1, high]`. If it's false, day `mid` is too late, and we must search for an earlier day in the range `[low, mid - 1]`. This process efficiently narrows down the search space until we pinpoint the last possible day.

```java
class Solution {
    public int lastDayToCross(int row, int col, int[][] cells) {
        int low = 1;
        int high = cells.length;
        int ans = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canCrossOnDay(row, col, cells, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean canCrossOnDay(int row, int col, int[][] cells, int day) {
        int[][] grid = new int[row][col];
        for (int i = 0; i < day; i++) {
            grid[cells[i][0] - 1][cells[i][1] - 1] = 1; // Mark as water
        }

        java.util.Queue<int[]> queue = new java.util.LinkedList<>();
        for (int c = 0; c < col; c++) {
            if (grid[0][c] == 0) {
                queue.offer(new int[]{0, c});
                grid[0][c] = -1; // Mark as visited
            }
        }

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

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0];
            int c = curr[1];

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

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

                if (nr >= 0 && nr < row && nc >= 0 && nc < col && grid[nr][nc] == 0) {
                    grid[nr][nc] = -1; // Mark as visited
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        return false;
    }
}
```
### Algorithm
*   The core idea is to binary search for the answer (the last day) in the range of possible days, from `0` to `row * col`.
*   Set `low = 0`, `high = row * col`, and `ans = 0`.
*   While `low <= high`:
    *   Calculate the middle day: `mid = low + (high - low) / 2`.
    *   Call a helper function `canCross(mid)` that checks if it's possible to cross on day `mid`.
    *   If `canCross(mid)` is `true`, it means day `mid` is a possible solution, and there might be an even later day. So, we record `mid` as our potential answer (`ans = mid`) and try the upper half of the search space (`low = mid + 1`).
    *   If `canCross(mid)` is `false`, it's impossible to cross on day `mid`, so we must look for an earlier day. We search the lower half (`high = mid - 1`).
*   After the loop terminates, `ans` will hold the maximum day on which crossing is possible.
*   The `canCross(day)` function is identical to the one used in the linear scan approach: it builds the grid for the given day and uses BFS/DFS to check for a path.

## Reverse Time with Union-Find
This approach provides the most optimal solution by reversing the problem. Instead of adding water and breaking connections, we start with a grid full of water and add land cells back one by one, in the reverse order they were flooded. This transforms the problem into one of adding connections, which is exactly what the Union-Find (DSU) data structure is designed to handle efficiently. We can find the first moment in this reversed timeline where the top and bottom of the grid become connected. That moment corresponds to the last day it was possible to cross in the original problem.
**Time:** O(row * col * α(row * col)), where α is the Inverse Ackermann function. Since α(N) is a very slow-growing function, it's considered nearly constant for all practical purposes. Thus, the complexity is effectively linear, O(row * col). · **Space:** O(row * col) for the Union-Find data structure's parent array and for the grid to keep track of land cells.
**Pros:** The most efficient solution with a nearly linear time complexity.; Avoids all redundant computations by incrementally building the connected components of land.
**Cons:** The logic is more complex and less intuitive than the previous approaches.; Requires knowledge of the Union-Find data structure.
### Explanation
We can reframe the problem: find the latest day `D` such that the set of land cells on that day, `L_D`, forms a connecting path from top to bottom. On day `D`, the land cells are precisely those that have not yet been flooded, i.e., `cells[D], cells[D+1], ..., cells[N-1]` where `N = row * col`.

This structure allows us to work backward from the end. We start with a grid that is entirely water. Then, for `i` from `N-1` down to `0`, we add the cell `cells[i]` back as land. As we add each land cell, we use a Union-Find data structure to merge its component with any adjacent land cells. 

We augment our DSU with two special nodes: a `source` connected to all top-row cells and a `sink` connected to all bottom-row cells. When a cell `(r, c)` becomes land, we union it with its land neighbors. If `r` is 0, we also union it with the `source`. If `r` is `row-1`, we union it with the `sink`. The moment `find(source) == find(sink)`, we have found a path connecting the top and bottom. Since we are iterating backward in time, the first time this condition is met corresponds to the latest day a path exists. The day number is simply the index `i` at which this occurs.

```java
class Solution {
    class DSU {
        int[] parent;
        public DSU(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        public int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }
        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
            }
        }
    }

    public int lastDayToCross(int row, int col, int[][] cells) {
        int n = row * col;
        DSU dsu = new DSU(n + 2);
        int topNode = n;
        int bottomNode = n + 1;
        int[][] grid = new int[row][col];
        int[] dr = {-1, 1, 0, 0, -1, -1, 1, 1};
        int[] dc = {0, 0, -1, 1, -1, 1, -1, 1};

        for (int i = n - 1; i >= 0; i--) {
            int r = cells[i][0] - 1;
            int c = cells[i][1] - 1;
            grid[r][c] = 1; // Mark as land
            int cellIndex = r * col + c;

            if (r == 0) {
                dsu.union(cellIndex, topNode);
            }
            if (r == row - 1) {
                dsu.union(cellIndex, bottomNode);
            }

            for (int j = 0; j < 8; j++) {
                int nr = r + dr[j];
                int nc = c + dc[j];
                if (nr >= 0 && nr < row && nc >= 0 && nc < col && grid[nr][nc] == 1) {
                    dsu.union(cellIndex, nr * col + nc);
                }
            }

            if (dsu.find(topNode) == dsu.find(bottomNode)) {
                return i;
            }
        }
        return 0; // Should not be reached given the constraints
    }
}
```
*Note: The code uses 8 directions for neighbors, which is also valid. The problem statement implies 4 cardinal directions, but connecting diagonally doesn't invalidate a path that uses cardinal directions.*
### Algorithm
*   The key insight is to process time in reverse. Instead of cells turning into water, we start with a fully flooded grid and turn cells back into land one by one.
*   We use a Union-Find (or Disjoint Set Union - DSU) data structure to efficiently track connected components of land cells.
*   Initialize a DSU structure with `row * col + 2` elements. `row * col` elements for the grid cells, one virtual `top` node, and one virtual `bottom` node.
*   Initialize a `grid` with all cells marked as water.
*   Iterate backward through the `cells` array, from index `i = cells.length - 1` down to `0`.
*   In each iteration `i`:
    *   Get the cell `(r, c)` from `cells[i]` (adjusting for 1-based indexing).
    *   Mark `(r, c)` as land in our grid.
    *   Get the 1D index for this cell, `idx = r * col + c`.
    *   For each of the 4 neighbors of `(r, c)` that are already land, perform a `union` operation between `idx` and the neighbor's index in the DSU.
    *   If the cell `(r, c)` is in the top row (`r == 0`), `union(idx, top_node)`.
    *   If the cell `(r, c)` is in the bottom row (`r == row - 1`), `union(idx, bottom_node)`.
    *   After performing the unions, check if the `top` and `bottom` virtual nodes are connected by calling `find(top_node) == find(bottom_node)`.
    *   If they are connected, it means a path from top to bottom has just been formed. Since we are iterating backward, this must be the last day a path exists. The answer is day `i` (if days are 0-indexed) or `i+1` (if 1-indexed). Based on problem examples, the answer is `i`.
*   Return `i` as soon as the connection is found.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
private
  int row;
private
  int col;
private
  boolean[][] grid;
private
  int[][] dirs = new int[][]{{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
public
  int latestDayToCross(int row, int col, int[][] cells) {
    int n = row * col;
    this.row = row;
    this.col = col;
    p = new int[n + 2];
    for (int i = 0; i < p.length; ++i) {
      p[i] = i;
    }
    grid = new boolean[row][col];
    int top = n, bottom = n + 1;
    for (int k = cells.length - 1; k >= 0; --k) {
      int i = cells[k][0] - 1, j = cells[k][1] - 1;
      grid[i][j] = true;
      for (int[] e : dirs) {
        if (check(i + e[0], j + e[1])) {
          p[find(i * col + j)] = find((i + e[0]) * col + j + e[1]);
        }
      }
      if (i == 0) {
        p[find(i * col + j)] = find(top);
      }
      if (i == row - 1) {
        p[find(i * col + j)] = find(bottom);
      }
      if (find(top) == find(bottom)) {
        return k;
      }
    }
    return 0;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
private
  boolean check(int i, int j) {
    return i >= 0 && i < row && j >= 0 && j < col && grid[i][j];
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  int dirs[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
  int row, col;
  int latestDayToCross(int row, int col, vector<vector<int>> &cells) {
    int n = row * col;
    this->row = row;
    this->col = col;
    p.resize(n + 2);
    for (int i = 0; i < p.size(); ++i)
      p[i] = i;
    vector<vector<bool>> grid(row, vector<bool>(col, false));
    int top = n, bottom = n + 1;
    for (int k = cells.size() - 1; k >= 0; --k) {
      int i = cells[k][0] - 1, j = cells[k][1] - 1;
      grid[i][j] = true;
      for (auto e : dirs) {
        if (check(i + e[0], j + e[1], grid)) {
          p[find(i * col + j)] = find((i + e[0]) * col + j + e[1]);
        }
      }
      if (i == 0)
        p[find(i * col + j)] = find(top);
      if (i == row - 1)
        p[find(i * col + j)] = find(bottom);
      if (find(top) == find(bottom))
        return k;
    }
    return 0;
  }
  bool check(int i, int j, vector<vector<bool>> &grid) {
    return i >= 0 && i < row && j >= 0 && j < col && grid[i][j];
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
};

```

### Python

```python
class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int: n = row * col p = list(range(n + 2)) grid = [[False] * col for _ in range(row)] top, bottom = n, n + 1 def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def check(i, j): return 0 <= i < row and 0 <= j < col and grid[i][j] for k in range(len(cells) - 1, - 1, - 1): i, j = cells[k][0] - 1, cells[k][1] - 1 grid[i][j] = True for x, y in [[0, 1], [0, - 1], [1, 0], [- 1, 0]]: if check(i + x, j + y): p[find(i * col + j)] = find((i + x) * col + j + y) if i == 0: p[find(i * col + j)] = find(top) if i == row - 1: p[find(i * col + j)] = find(bottom) if find(top) == find(bottom): return k return 0

```