Watch 10 video solutions for Last Day Where You Can Still Cross, a hard level problem involving Array, Binary Search, Depth-First Search. This walkthrough by codestorywithMIK has 10,774 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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:
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:
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 * 1044 <= row * col <= 2 * 104cells.length == row * col1 <= ri <= row1 <= ci <= colcells are unique.Problem Overview: A grid starts as land. Each day, one cell becomes water. You must find the last day when it is still possible to walk from the top row to the bottom row using only land cells moving in four directions.
The key observation: if crossing is possible on day d, it is also possible on every earlier day. Once the grid becomes too flooded, crossing stays impossible afterward. This monotonic behavior allows a binary search on the day number.
Approach 1: Binary Search with DFS/BFS (O(m * n log(m * n)) time, O(m * n) space)
Binary search the answer between day 1 and m * n. For each candidate day, construct the grid where the first day cells in cells are flooded. Start from every land cell in the top row and run DFS or BFS to check if you can reach the bottom row. The traversal only moves through land cells and marks visited positions to avoid repetition. If a path exists, crossing is still possible, so move the binary search window right. Otherwise move left. This approach is straightforward and maps directly to graph traversal on a matrix.
Approach 2: Binary Search with Union-Find (O(m * n log(m * n)) time, O(m * n) space)
Instead of exploring the grid with DFS each time, treat each cell as a node in a Union-Find structure. For a given day in the binary search, mark flooded cells and union adjacent land cells. Two virtual nodes represent the top boundary and bottom boundary. Land cells in the first row connect to the top node, and cells in the last row connect to the bottom node. If both virtual nodes end up in the same connected component, a path from top to bottom exists. Union-Find reduces repeated traversal work and keeps connectivity checks near constant time.
Recommended for interviews: Binary Search with DFS/BFS is usually expected first because it clearly demonstrates the monotonic property and grid traversal logic. After establishing correctness, Union-Find shows deeper understanding of connectivity problems and can lead to cleaner connectivity checks in dense grids.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search + DFS/BFS | O(m * n log(m * n)) | O(m * n) | Best starting approach for interviews. Simple grid traversal and easy to implement. |
| Binary Search + Union-Find | O(m * n log(m * n)) | O(m * n) | When frequent connectivity checks are needed. Cleaner path existence checks using disjoint sets. |