Sponsored
Sponsored
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.
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.
1import java.util.*;
2
3class Solution {
4 private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
5 private int row, col;
6 private int[][] grid;
7
8 private boolean isValid(int x, int y) {
9 return x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == 0;
10 }
11
12 private boolean dfs(int x, int y) {
13 if (x == row - 1) return true;
14 grid[x][y] = 1;
15 for (int[] direction : directions) {
16 int newX = x + direction[0], newY = y + direction[1];
17 if (isValid(newX, newY) && dfs(newX, newY)) return true;
18 }
19 return false;
20 }
21
22 private boolean canCross(int day, int[][] cells) {
23 grid = new int[row][col];
24 for (int i = 0; i <= day; ++i) grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
25 for (int i = 0; i < col; ++i)
26 if (grid[0][i] == 0 && dfs(0, i)) return true;
27 return false;
28 }
29
30 public int latestDayToCross(int row, int col, int[][] cells) {
31 this.row = row;
32 this.col = col;
33 int left = 0, right = cells.length - 1, result = 0;
34 while (left <= right) {
35 int mid = left + (right - left) / 2;
36 if (canCross(mid, cells)) {
37 result = mid;
38 left = mid + 1;
39 } else {
40 right = mid - 1;
41 }
42 }
43 return result + 1;
44 }
45}
46This Java solution uses binary search and checks for path connectivity using DFS on a simulated grid. Each day up to the midpoint in the binary search, the grid is flooded, and DFS checks for a path from top to bottom.
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.
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.
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;
}
}
The C# solution is constructed around union-find data structures, simultaneously processing each grid flood condition to determine connectivity and ultimately the latest walkable day through a binary search routine.