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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
Last Day Where You Can Still Cross | BFS | DFS | Binary Search | GOOGLE Onsite | Leetcode-1970 • codestorywithMIK • 3,947 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