Last Day Where You Can Still Cross
HardPrompt
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 <= col- All the values of
cellsare unique.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize
ans = 0. - Loop through each day
dfrom1torow * col. - For each day
d, create a grid representing the state of land and water. This involves marking cellscells[0]throughcells[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)returnstrue, it means it's possible to cross on dayd, so we update our potential answer:ans = d. - If
pathExists(grid)returnsfalse, 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
visited2D 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 returntrue. - 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.
- Dequeue a cell
- If the queue becomes empty and the bottom row was not reached, it means no path exists. Return
false.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- The core idea is to binary search for the answer (the last day) in the range of possible days, from
0torow * col. - Set
low = 0,high = row * col, andans = 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 daymid. - If
canCross(mid)istrue, it means daymidis a possible solution, and there might be an even later day. So, we recordmidas our potential answer (ans = mid) and try the upper half of the search space (low = mid + 1). - If
canCross(mid)isfalse, it's impossible to cross on daymid, so we must look for an earlier day. We search the lower half (high = mid - 1).
- Calculate the middle day:
- After the loop terminates,
answill 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.
Walkthrough
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:
- Create a
row x colgrid. - Flood the cells that become water by day
mid. These arecells[0]throughcells[mid-1]. - 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.
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; }}Complexity
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.
Trade-offs
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.
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.
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 + 2elements.row * colelements for the grid cells, one virtualtopnode, and one virtualbottomnode. - Initialize a
gridwith all cells marked as water. - Iterate backward through the
cellsarray, from indexi = cells.length - 1down to0. - In each iteration
i:- Get the cell
(r, c)fromcells[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 aunionoperation betweenidxand 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
topandbottomvirtual nodes are connected by callingfind(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) ori+1(if 1-indexed). Based on problem examples, the answer isi.
- Get the cell
- Return
ias soon as the connection is found.
Walkthrough
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.
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.
Complexity
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.
Trade-offs
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.
Solutions
Solution
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]; }}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]; }};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 0Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.