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.
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]; }}Video 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.