Last Day Where You Can Still Cross solution and explanation
Google
9 more videos on this problem
Last Day Where You Can Still Cross | BFS | DFS | Binary Search | Leetcode 1970 | codestorywithMIKcodestorywithMIK · 29:09 · 11K views
Last Day Where You Can Still Cross | LeetCode 1970 | Not a Hard ProblemSanyam IIT Guwahati · 17:54 · 1K views
Last Day Where You Can Still Cross - Leetcode 1970 - PythonTechError · 10:41 · 1K views
LeetCode 1970 Last Day Where You Can Still Cross | Google Microsoft Facebook InterviewJeevan Kumar - Cracckify · 13:59 · 1K views
Last Day Where You Can Still Cross | LeetCode 1970 | Coders CampCoders Camp · 13:21 · 1K views
Last Day Where You Can Still Cross | Disjoint Set | Binary Search | Multi Source BFS | Leetcode 1970Techdose · 47:04 · 1K views
1970. Last Day Where You Can Still Cross (Leetcode Hard)Programming Live with Larry · 21:06 · 1K views
1970. Last Day Where You Can Still Cross | Leetcode Daily - PythonLeetcode Daily · 9:05 · 462 views
Last Day Where You Can Still Cross 🔥 | LeetCode 1970 | Binary Search + BFS Study Placement · 33:41 · 405 views
Last Day Where You Can Still Cross | | LeetCode 1970 | Union Find Approach | JavaThe TryIt Project · 24:20 · 292 views
The problem
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.
Approach overview
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 1: Binary Search with DFS
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.
class Solution:
def latestDayToCross(self, row, col, cells):
def canCross(day):
grid = [[0] * col for _ in range(row)]
for r, c in cells[:day]:
grid[r - 1][c - 1] = 1
stack = [(0, c) for c in range(col) if grid[0][c] == 0]
visited = set(stack)
while stack:
r, c = stack.pop()
if r == row - 1:
return True
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < row and 0 <= nc < col and grid[nr][nc] == 0 and (nr, nc) not in visited:
visited.add((nr, nc))
stack.append((nr, nc))
return False
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
left, right = 0, len(cells)
while left < right:
mid = (left + right) // 2
if canCross(mid):
left = mid + 1
else:
right = mid
return leftimport java.util.*;
class Solution {
private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private int row, col;
private int[][] grid;
private boolean isValid(int x, int y) {
return x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == 0;
}
private boolean dfs(int x, int y) {
if (x == row - 1) return true;
grid[x][y] = 1;
for (int[] direction : directions) {
int newX = x + direction[0], newY = y + direction[1];
if (isValid(newX, newY) && dfs(newX, newY)) return true;
}
return false;
}
private boolean canCross(int day, int[][] cells) {
grid = new int[row][col];
for (int i = 0; i <= day; ++i) grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
for (int i = 0; i < col; ++i)
if (grid[0][i] == 0 && dfs(0, i)) return true;
return false;
}
public int latestDayToCross(int row, int col, int[][] cells) {
this.row = row;
this.col = col;
int left = 0, right = cells.length - 1, result = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canCross(mid, cells)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result + 1;
}
}#include <vector>
#include <queue>
#include <cstring>
using namespace std;
class Solution {
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
vector<vector<int>> grid;
int r, c;
bool valid(int x, int y) {
return x >= 0 && x < r && y >= 0 && y < c && grid[x][y] == 0;
}
bool dfs(int x, int y) {
if (x == r - 1) return true;
grid[x][y] = 1;
for (auto d : directions) {
int nx = x + d.first, ny = y + d.second;
if (valid(nx, ny) && dfs(nx, ny)) return true;
}
return false;
}
bool canCross(int day, vector<vector<int>>& cells) {
grid = vector<vector<int>>(r, vector<int>(c, 0));
for (int i = 0; i <= day; ++i) grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
for (int i = 0; i < c; ++i)
if (grid[0][i] == 0 && dfs(0, i)) return true;
return false;
}
public:
int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
r = row, c = col;
int left = 0, right = cells.size() - 1, last = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canCross(mid, cells)) {
last = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return last + 1;
}
};var latestDayToCross = function(row, col, cells) {
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
let grid, r, c;
const isValid = (x, y) => {
return x >= 0 && x < r && y >= 0 && y < c && grid[x][y] === 0;
};
const dfs = (x, y) => {
if (x === r - 1) return true;
grid[x][y] = 1;
for (const [dx, dy] of directions) {
const nx = x + dx, ny = y + dy;
if (isValid(nx, ny) && dfs(nx, ny)) return true;
}
return false;
};
const canCross = (day) => {
grid = Array.from({ length: row }, () => Array(col).fill(0));
for (let i = 0; i <= day; i++) {
grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
}
for (let i = 0; i < col; i++) {
if (grid[0][i] === 0 && dfs(0, i)) return true;
}
return false;
};
let left = 0, right = cells.length - 1, lastValidDay = 0;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (canCross(mid)) {
lastValidDay = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return lastValidDay + 1;
};#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX 20000
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool visited[MAX][MAX];
bool isValid(int x, int y, int row, int col, int matrix[MAX][MAX]) {
return (x >= 0 && x < row && y >= 0 && y < col && matrix[x][y] == 0 && !visited[x][y]);
}
bool dfs(int x, int y, int row, int col, int matrix[MAX][MAX]) {
if (x == row - 1) return true;
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int newX = x + directions[i][0];
int newY = y + directions[i][1];
if (isValid(newX, newY, row, col, matrix)) {
if (dfs(newX, newY, row, col, matrix)) return true;
}
}
return false;
}
bool canCross(int row, int col, int cells[][2], int day, int matrix[MAX][MAX]) {
memset(matrix, 0, sizeof(int) * MAX * MAX);
memset(visited, false, sizeof(bool) * MAX * MAX);
for (int i = 0; i <= day; i++) {
matrix[cells[i][0] - 1][cells[i][1] - 1] = 1;
}
for (int i = 0; i < col; i++) {
if (matrix[0][i] == 0 && dfs(0, i, row, col, matrix)) return true;
}
return false;
}
int latestDayToCross(int row, int col, int cells[][2], int cellsSize) {
int matrix[MAX][MAX];
int left = 0, right = cellsSize - 1;
int result = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canCross(row, col, cells, mid, matrix)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result + 1;
}
int main() {
int row = 2, col = 2;
int cells[4][2] = {{1, 1}, {2, 1}, {1, 2}, {2, 2}};
printf("%d\n", latestDayToCross(row, col, cells, 4));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
private int[][] directions = new int[][] {
new int[] {0, 1}, new int[] {1, 0}, new int[] {0, -1}, new int[] {-1, 0}
};
private int row, col;
private bool CanCross(int[][] grid, int r, int c) {
var stack = new Stack<(int, int)>();
stack.Push((0, c));
bool[,] visited = new bool[row, col];
visited[0, c] = true;
while (stack.Count > 0) {
var (x, y) = stack.Pop();
if (x == row - 1) return true;
foreach (var d in directions) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && ny >= 0 && nx < row && ny < col && !visited[nx, ny] && grid[nx][ny] == 0) {
visited[nx, ny] = true;
stack.Push((nx, ny));
}
}
}
return false;
}
public int LatestDayToCross(int row, int col, int[][] cells) {
this.row = row;
this.col = col;
int left = 0, right = cells.Length;
while (left < right) {
int mid = (left + right) / 2;
var grid = new int[row][];
for (int i = 0; i < row; ++i) grid[i] = new int[col];
for (int i = 0; i < mid; ++i) grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
bool canCross = false;
for (int i = 0; i < col; ++i) {
if (grid[0][i] == 0 && CanCross(grid, 0, i)) {
canCross = true;
break;
}
}
if (canCross) left = mid + 1;
else right = mid;
}
return left;
}
}In this Python example, we use binary search paired with DFS to check path presence using a stack for each midpoint in the binary search. The flooded grid is backtracked for the last path feasible day.
Time Complexity is O(n * m * log(n * m)) and Space Complexity is O(n * m), given n rows and m columns.
Approach 2: Binary Search with Union-Find
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.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path compression
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
class Solution:
def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
size = row * col
def canCross(day):
uf = UnionFind(size + 2)
grid = [[0] * col for _ in range(row)]
for r, c in cells[:day]:
grid[r - 1][c - 1] = 1
for r in range(row):
for c in range(col):
if grid[r][c] == 0:
index = r * col + c
if r == 0:
uf.union(index, size) # Connect to top virtual node
if r == row - 1:
uf.union(index, size + 1) # Connect to bottom virtual node
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < row and 0 <= nc < col and grid[nr][nc] == 0:
uf.union(index, nr * col + nc)
return uf.find(size) == uf.find(size + 1)
left, right = 0, len(cells)
while left < right:
mid = (left + right) // 2
if canCross(mid):
left = mid + 1
else:
right = mid
return left - 1import java.util.*;
class Solution {
private int find(int[] parent, int x) {
if (parent[x] != x) parent[x] = find(parent, parent[x]);
return parent[x];
}
private void unionSet(int[] parent, int[] rank, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
public int latestDayToCross(int row, int col, int[][] cells) {
int[] parent = new int[row * col + 2];
int[] rank = new int[row * col + 2];
for (int i = 0; i < parent.length; ++i) parent[i] = i;
int left = 0, right = cells.length;
int top_virtual = row * col, bottom_virtual = row * col + 1;
while (left < right) {
int mid = left + (right - left) / 2;
int[][] grid = new int[row][col];
for (int i = 0; i < mid; ++i) {
grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
}
for (int r = 0; r < row; ++r) {
for (int c = 0; c < col; ++c) {
if (grid[r][c] == 0) {
int index = r * col + c;
if (r == 0) unionSet(parent, rank, index, top_virtual);
if (r == row - 1) unionSet(parent, rank, index, bottom_virtual);
if (r > 0 && grid[r - 1][c] == 0) unionSet(parent, rank, index, index - col);
if (c > 0 && grid[r][c - 1] == 0) unionSet(parent, rank, index, index - 1);
}
}
}
if (find(parent, top_virtual) == find(parent, bottom_virtual)) {
left = mid + 1;
} else {
right = mid;
}
// Reset parent array for the next day calculation
for (int i = 0; i < parent.length; ++i) parent[i] = i;
}
return left - 1;
}
}#include <vector>
#include <numeric>
using namespace std;
class Solution {
public:
int find(vector<int>& parent, int i) {
if (parent[i] != i) parent[i] = find(parent, parent[i]);
return parent[i];
}
void unionSet(vector<int>& parent, vector<int>& rank, int i, int j) {
int rootI = find(parent, i);
int rootJ = find(parent, j);
if (rootI != rootJ) {
if (rank[rootI] > rank[rootJ]) {
parent[rootJ] = rootI;
} else if (rank[rootI] < rank[rootJ]) {
parent[rootI] = rootJ;
} else {
parent[rootJ] = rootI;
rank[rootI]++;
}
}
}
bool canCross(int day, vector<vector<int>>& cells, int r, int c) {
int size = r * c;
vector<int> parent(size + 2);
vector<int> rank(size + 2, 0);
iota(parent.begin(), parent.end(), 0);
int top_virtual = size;
int bottom_virtual = size + 1;
vector<vector<int>> grid(r, vector<int>(c, 0));
for (int i = 0; i < day; i++) {
grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (grid[i][j] == 0) {
int currentIdx = i * c + j;
if (i == 0) unionSet(parent, rank, currentIdx, top_virtual);
if (i == r - 1) unionSet(parent, rank, currentIdx, bottom_virtual);
if (i > 0 && grid[i - 1][j] == 0) unionSet(parent, rank, currentIdx - c, currentIdx);
if (j > 0 && grid[i][j - 1] == 0) unionSet(parent, rank, currentIdx - 1, currentIdx);
if (i < r - 1 && grid[i + 1][j] == 0) unionSet(parent, rank, currentIdx + c, currentIdx);
if (j < c - 1 && grid[i][j + 1] == 0) unionSet(parent, rank, currentIdx + 1, currentIdx);
}
}
}
return find(parent, top_virtual) == find(parent, bottom_virtual);
}
int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
int left = 0, right = cells.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (canCross(mid, cells, row, col)) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
};class UnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
}
}
}
var latestDayToCross = function(row, col, cells) {
const size = row * col;
const uf = new UnionFind(size + 2);
const top_virtual = size;
const bottom_virtual = size + 1;
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
const canCross = (mid) => {
const grid = Array.from({ length: row }, () => Array(col).fill(0));
for (let i = 0; i < mid; i++) {
const [r, c] = cells[i];
grid[r - 1][c - 1] = 1;
}
for (let r = 0; r < row; r++) {
for (let c = 0; c < col; c++) {
if (grid[r][c] === 0) {
const index = r * col + c;
if (r === 0) uf.union(index, top_virtual);
if (r === row - 1) uf.union(index, bottom_virtual);
for (const [dr, dc] of directions) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < row && nc >= 0 && nc < col && grid[nr][nc] === 0) {
uf.union(index, nr * col + nc);
}
}
}
}
}
return uf.find(top_virtual) === uf.find(bottom_virtual);
}
let left = 0, right = cells.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (canCross(mid)) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
};#include <stdio.h>
#include <stdbool.h>
#define MAX 20000
int parent[MAX];
int rank[MAX];
int find(int x) {
return parent[x] == x ? x : (parent[x] = find(parent[x]));
}
void unionSet(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
bool canCross(int day, int row, int col, int cells[][2]) {
for (int i = 0; i < row * col + 2; ++i) {
parent[i] = i;
rank[i] = 0;
}
const int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int top_virtual = row * col;
int bottom_virtual = row * col + 1;
for (int i = 0; i < day; i++) {
int r = cells[i][0] - 1;
int c = cells[i][1] - 1;
int currentIdx = r * col + c;
for (int j = 0; j < 4; j++) {
int nr = r + directions[j][0];
int nc = c + directions[j][1];
if (nr >= 0 && nr < row && nc >= 0 && nc < col) {
int neighborIdx = nr * col + nc;
if (find(neighborIdx) != find(currentIdx)) {
unionSet(currentIdx, neighborIdx);
}
}
}
if (r == 0) {
unionSet(currentIdx, top_virtual);
}
if (r == row - 1) {
unionSet(currentIdx, bottom_virtual);
}
if (find(top_virtual) == find(bottom_virtual)) return true;
}
return false;
}
int latestDayToCross(int row, int col, int cells[][2], int cellsSize) {
int left = 0, right = cellsSize;
while (left < right) {
int mid = left + (right - left) / 2;
if (canCross(mid, row, col, cells)) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
int main() {
int row = 2, col = 2;
int cells[4][2] = {{1, 1}, {2, 1}, {1, 2}, {2, 2}};
printf("%d\n", latestDayToCross(row, col, cells, 4));
return 0;
}using System;
public class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public void Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}
public class Solution {
public int LatestDayToCross(int row, int col, int[][] cells) {
int size = row * col;
var uf = new UnionFind(size + 2);
int top_virtual = size;
int bottom_virtual = size + 1;
for (int left = 0, right = cells.Length; left < right;) {
int mid = left + (right - left) / 2;
var grid = new int[row, col];
Array.Clear(uf.parent, 0, uf.parent.Length);
for (int i = 0; i < uf.parent.Length; ++i) uf.parent[i] = i;
for (int i = 0; i < mid; ++i) {
grid[cells[i][0] - 1, cells[i][1] - 1] = 1;
}
for (int r = 0; r < row; ++r) {
for (int c = 0; c < col; ++c) {
if (grid[r, c] == 0) {
int index = r * col + c;
if (r == 0) {
uf.Union(index, top_virtual);
}
if (r == row - 1) {
uf.Union(index, bottom_virtual);
}
if (r > 0 && grid[r - 1, c] == 0) {
uf.Union((r - 1) * col + c, index);
}
if (c > 0 && grid[r, c - 1] == 0) {
uf.Union(r * col + (c - 1), index);
}
}
}
}
if (uf.Find(top_virtual) == uf.Find(bottom_virtual)) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
}This Python example leverages a union-find data structure to track connectivity across floodable days, marking the last possible cross day once the virtual nodes disconnect.
Time Complexity is O(n * m * log(n * m)) due to union-find path compression and union operations. Space Complexity O(n * m) accounts for union-find storage requirements.
Approach 3: Binary Search + BFS
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.
function latestDayToCross(row: number, col: number, cells: number[][]): number {
let [l, r] = [1, cells.length];
const check = (k: number): boolean => {
const g: number[][] = Array.from({ length: row }, () => Array(col).fill(0));
for (let i = 0; i < k; ++i) {
const [x, y] = cells[i];
g[x - 1][y - 1] = 1;
}
const q: number[][] = [];
for (let j = 0; j < col; ++j) {
if (g[0][j] === 0) {
q.push([0, j]);
g[0][j] = 1;
}
}
const dirs: number[] = [-1, 0, 1, 0, -1];
for (const [x, y] of q) {
if (x === row - 1) {
return true;
}
for (let i = 0; i < 4; ++i) {
const nx = x + dirs[i];
const ny = y + dirs[i + 1];
if (nx >= 0 && nx < row && ny >= 0 && ny < col && g[nx][ny] === 0) {
q.push([nx, ny]);
g[nx][ny] = 1;
}
}
}
return false;
};
while (l < r) {
const mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}func latestDayToCross(row int, col int, cells [][]int) int {
l, r := 1, len(cells)
dirs := [5]int{-1, 0, 1, 0, -1}
check := func(k int) bool {
g := make([][]int, row)
for i := range g {
g[i] = make([]int, col)
}
for i := 0; i < k; i++ {
g[cells[i][0]-1][cells[i][1]-1] = 1
}
q := [][2]int{}
for j := 0; j < col; j++ {
if g[0][j] == 0 {
g[0][j] = 1
q = append(q, [2]int{0, j})
}
}
for len(q) > 0 {
x, y := q[0][0], q[0][1]
q = q[1:]
if x == row-1 {
return true
}
for i := 0; i < 4; i++ {
nx, ny := x+dirs[i], y+dirs[i+1]
if nx >= 0 && nx < row && ny >= 0 && ny < col && g[nx][ny] == 0 {
g[nx][ny] = 1
q = append(q, [2]int{nx, ny})
}
}
}
return false
}
for l < r {
mid := (l + r + 1) >> 1
if check(mid) {
l = mid
} else {
r = mid - 1
}
}
return l
}use std::collections::VecDeque;
impl Solution {
pub fn latest_day_to_cross(row: i32, col: i32, cells: Vec<Vec<i32>>) -> i32 {
let mut l: i32 = 1;
let mut r: i32 = cells.len() as i32;
let m = row as usize;
let n = col as usize;
let check = |k: i32, cells: &Vec<Vec<i32>>| -> bool {
let mut g = vec![vec![0i32; n]; m];
for i in 0..k as usize {
let x = (cells[i][0] - 1) as usize;
let y = (cells[i][1] - 1) as usize;
g[x][y] = 1;
}
let dirs = [-1, 0, 1, 0, -1];
let mut q: VecDeque<(usize, usize)> = VecDeque::new();
for j in 0..n {
if g[0][j] == 0 {
q.push_back((0, j));
g[0][j] = 1;
}
}
while let Some((x, y)) = q.pop_front() {
if x == m - 1 {
return true;
}
for i in 0..4 {
let nx = x as i32 + dirs[i];
let ny = y as i32 + dirs[i + 1];
if nx >= 0
&& nx < m as i32
&& ny >= 0
&& ny < n as i32
&& g[nx as usize][ny as usize] == 0
{
q.push_back((nx as usize, ny as usize));
g[nx as usize][ny as usize] = 1;
}
}
}
false
};
while l < r {
let mid = (l + r + 1) >> 1;
if check(mid, &cells) {
l = mid;
} else {
r = mid - 1;
}
}
l
}
}Approach 4: Union-Find
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.
class UnionFind {
p: number[];
size: number[];
constructor(n: number) {
this.p = Array(n)
.fill(0)
.map((_, i) => i);
this.size = Array(n).fill(1);
}
find(x: number): number {
if (this.p[x] !== x) {
this.p[x] = this.find(this.p[x]);
}
return this.p[x];
}
union(a: number, b: number): boolean {
const [pa, pb] = [this.find(a), this.find(b)];
if (pa === pb) {
return false;
}
if (this.size[pa] > this.size[pb]) {
this.p[pb] = pa;
this.size[pa] += this.size[pb];
} else {
this.p[pa] = pb;
this.size[pb] += this.size[pa];
}
return true;
}
}
function latestDayToCross(row: number, col: number, cells: number[][]): number {
const mn = cells.length;
const uf = new UnionFind(row * col + 2);
const [s, t] = [mn, mn + 1];
const g: number[][] = Array.from({ length: row }, () => Array(col).fill(1));
const dirs: number[] = [-1, 0, 1, 0, -1];
for (let i = mn - 1; ; --i) {
const [x, y] = [cells[i][0] - 1, cells[i][1] - 1];
g[x][y] = 0;
for (let j = 0; j < 4; ++j) {
const [nx, ny] = [x + dirs[j], y + dirs[j + 1]];
if (nx >= 0 && nx < row && ny >= 0 && ny < col && g[nx][ny] === 0) {
uf.union(x * col + y, nx * col + ny);
}
}
if (x === 0) {
uf.union(s, y);
}
if (x === row - 1) {
uf.union(t, x * col + y);
}
if (uf.find(s) === uf.find(t)) {
return i;
}
}
}type unionFind struct {
p, size []int
}
func newUnionFind(n int) *unionFind {
p := make([]int, n)
size := make([]int, n)
for i := range p {
p[i] = i
size[i] = 1
}
return &unionFind{p, size}
}
func (uf *unionFind) find(x int) int {
if uf.p[x] != x {
uf.p[x] = uf.find(uf.p[x])
}
return uf.p[x]
}
func (uf *unionFind) union(a, b int) bool {
pa, pb := uf.find(a), uf.find(b)
if pa == pb {
return false
}
if uf.size[pa] > uf.size[pb] {
uf.p[pb] = pa
uf.size[pa] += uf.size[pb]
} else {
uf.p[pa] = pb
uf.size[pb] += uf.size[pa]
}
return true
}
func latestDayToCross(row int, col int, cells [][]int) int {
mn := len(cells)
uf := newUnionFind(mn + 2)
s, t := mn, mn+1
g := make([][]int, row)
for i := range g {
g[i] = make([]int, col)
for j := range g[i] {
g[i][j] = 1
}
}
dirs := [5]int{-1, 0, 1, 0, -1}
for i := mn - 1; ; i-- {
x, y := cells[i][0]-1, cells[i][1]-1
g[x][y] = 0
for j := 0; j < 4; j++ {
nx, ny := x+dirs[j], y+dirs[j+1]
if nx >= 0 && nx < row && ny >= 0 && ny < col && g[nx][ny] == 0 {
uf.union(x*col+y, nx*col+ny)
}
}
if x == 0 {
uf.union(s, x*col+y)
}
if x == row-1 {
uf.union(t, x*col+y)
}
if uf.find(s) == uf.find(t) {
return i
}
}
}struct UnionFind {
p: Vec<usize>,
size: Vec<usize>,
}
impl UnionFind {
fn new(n: usize) -> Self {
let mut p = vec![0; n];
let mut size = vec![1; n];
for i in 0..n {
p[i] = i;
}
Self { p, size }
}
fn find(&mut self, x: usize) -> usize {
if self.p[x] != x {
let px = self.p[x];
self.p[x] = self.find(px);
}
self.p[x]
}
fn union(&mut self, a: usize, b: usize) -> bool {
let pa = self.find(a);
let pb = self.find(b);
if pa == pb {
return false;
}
if self.size[pa] > self.size[pb] {
self.p[pb] = pa;
self.size[pa] += self.size[pb];
} else {
self.p[pa] = pb;
self.size[pb] += self.size[pa];
}
true
}
}
impl Solution {
pub fn latest_day_to_cross(row: i32, col: i32, cells: Vec<Vec<i32>>) -> i32 {
let mn = cells.len();
let mut uf = UnionFind::new(mn + 2);
let s = mn;
let t = mn + 1;
let row = row as usize;
let col = col as usize;
let mut g = vec![vec![1i32; col]; row];
let dirs = [-1, 0, 1, 0, -1];
let mut i = mn as i32 - 1;
loop {
let x = (cells[i as usize][0] - 1) as usize;
let y = (cells[i as usize][1] - 1) as usize;
g[x][y] = 0;
for j in 0..4 {
let nx = x as i32 + dirs[j];
let ny = y as i32 + dirs[j + 1];
if nx >= 0
&& nx < row as i32
&& ny >= 0
&& ny < col as i32
&& g[nx as usize][ny as usize] == 0
{
uf.union(x * col + y, nx as usize * col + ny as usize);
}
}
if x == 0 {
uf.union(s, x * col + y);
}
if x == row - 1 {
uf.union(t, x * col + y);
}
if uf.find(s) == uf.find(t) {
return i;
}
i -= 1;
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search with DFS | Time Complexity is O(n * m * log(n * m)) and Space Complexity is O(n * m), given n rows and m columns. |
| Binary Search with Union-Find | Time Complexity is O(n * m * log(n * m)) due to union-find path compression and union operations. Space Complexity O(n * m) accounts for union-find storage requirements. |
| Binary Search + BFS | – |
| Union-Find | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Last Day Where You Can Still Cross easy or hard?
Last Day Where You Can Still Cross is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the monotonic property that enables binary search and efficiently checking connectivity in a dynamically flooding grid.
Last Day Where You Can Still Cross Python/Java solution
Python and Java implementations typically perform binary search over the day index and rebuild the grid for each check. A DFS/BFS explores reachable land cells from the top row. Java solutions often use iterative BFS with queues, while Python versions commonly use DFS recursion or deque-based BFS.
How to solve Last Day Where You Can Still Cross in O(n)?
A near-linear approach uses Union-Find while processing cells in reverse order (from the last day backward). Each step converts water back to land and unions adjacent land cells. Connectivity between top and bottom boundaries is checked after each step, giving roughly O(m*n α(m*n)) time where α is the inverse Ackermann function.
What is the best approach for Last Day Where You Can Still Cross?
Binary Search combined with DFS or BFS is the most common approach. The key insight is that the ability to cross the grid is monotonic with respect to the day number. Binary search finds the last valid day, while DFS/BFS checks whether a path from the top row to the bottom row exists in O(m*n) time for each check.
Is Last Day Where You Can Still Cross asked at Google/Amazon/Meta?
This problem style appears frequently in interviews at large tech companies including Google, Amazon, and Meta. It tests binary search on answers, grid traversal, and connectivity structures like Union-Find, all common interview patterns for graph and matrix problems.
What data structure is used in Last Day Where You Can Still Cross?
The solution commonly uses a grid matrix with DFS or BFS traversal, combined with binary search over days. An alternative approach uses the Union-Find (Disjoint Set Union) data structure to efficiently track connectivity between cells.
What is the time complexity of Last Day Where You Can Still Cross?
The typical solution runs in O(m * n log(m * n)) time. Binary search performs about log(m*n) checks, and each check runs a grid traversal such as DFS or BFS that touches up to m*n cells. Space complexity is O(m*n) for the grid and visited tracking.