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.
This approach involves using a binary search to find the last day a path exists from top to bottom. For each midpoint in the binary search, simulate the grid's flooding and check path connectivity using Depth First Search (DFS). Start by initializing the grid as land then flood the cells according to the days up to midpoint. Using DFS, attempt to find a path from the top to the bottom row.
This C implementation utilizes binary search to identify the last day on which a path exists. A DFS is performed on each iteration to verify path connectivity. The matrix is simulated up to the nth day for the selected midpoint during binary search.
Time Complexity is O(n * m * log(n * m)) where n is the number of rows and m is the number of columns. Space Complexity is O(n * m) for the visited matrix.
This approach involves using a union-find data structure to efficiently check connectivity between the top and bottom rows during a binary search over the days. For each day in the binary search, the cells flooded up to that day are processed, and union operations are performed on adjacent land cells. We add virtual top and bottom nodes in the union-find structure to track connectivity between the top and bottom row cells.
This C code uses union-find to efficiently manage connectivity between cells during binary search on flooding days. Virtual top and bottom nodes simulate the start and finish of paths, confirming connectivity between them.
Time Complexity is O(n * m * log(n * m)) due to union-find operations, and Space Complexity is O(n * m) for the union-find parent and rank tracking.
We note that if we can walk from the top row to the bottom row on day k, then for any 0 < k' < k, we can also walk from the top row to the bottom row on day k'. This exhibits monotonicity, so we can use binary search to find the largest k such that we can walk from the top row to the bottom row on day k.
We define the left boundary of the binary search as l = 1 and the right boundary as r = |cells|, where |cells| represents the length of the array cells. Then, we perform binary search on k. For each k, we take the first k elements of cells, turn the corresponding cells into water, and then use breadth-first search (BFS) to try to walk from the top row to the bottom row. If we can reach the bottom row, it means we can walk from the top row to the bottom row on day k, so we update the left boundary l to k. Otherwise, we update the right boundary r to k - 1.
The time complexity is O(m times n times log (m times n)), and the space complexity is O(m times n). Here, m and n represent the number of rows and columns of the matrix, respectively.
We can first initialize all land cells as 1, then traverse the array cells in reverse order, turning each corresponding land cell into 0 and merging it with the adjacent land cells (up, down, left, right). We also need to maintain two virtual nodes s and t, representing the virtual nodes for the top row and the bottom row, respectively. If s and t are connected in the union-find set, it means we can walk from the top row to the bottom row on day i.
The time complexity is O(m times n times \alpha(m times n)), and the space complexity is O(m times n). Here, m and n represent the number of rows and columns of the matrix, respectively, and \alpha represents the inverse Ackermann function.
| Approach | Complexity |
|---|---|
| Binary Search with DFS | Time Complexity is O(n * m * log(n * m)) where n is the number of rows and m is the number of columns. Space Complexity is O(n * m) for the visited matrix. |
| Binary Search with Union-Find | Time Complexity is O(n * m * log(n * m)) due to union-find operations, and Space Complexity is O(n * m) for the union-find parent and rank tracking. |
| Binary Search + BFS | — |
| Union-Find | — |
| 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. |
Last Day Where You Can Still Cross | BFS | DFS | Binary Search | Leetcode 1970 | codestorywithMIK • codestorywithMIK • 10,774 views views
Watch 9 more video solutions →Practice Last Day Where You Can Still Cross with our built-in code editor and test cases.
Practice on FleetCode