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.
1class Solution:
2 def latestDayToCross(self, row, col, cells):
3 def canCross(day):
4 grid = [[0] * col for _ in range(row)]
5 for r, c in cells[:day]:
6 grid[r - 1][c - 1] = 1
7
8 stack = [(0, c) for c in range(col) if grid[0][c] == 0]
9 visited = set(stack)
10 while stack:
11 r, c = stack.pop()
12 if r == row - 1:
13 return True
14 for dr, dc in directions:
15 nr, nc = r + dr, c + dc
16 if 0 <= nr < row and 0 <= nc < col and grid[nr][nc] == 0 and (nr, nc) not in visited:
17 visited.add((nr, nc))
18 stack.append((nr, nc))
19 return False
20
21 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
22 left, right = 0, len(cells)
23 while left < right:
24 mid = (left + right) // 2
25 if canCross(mid):
26 left = mid + 1
27 else:
28 right = mid
29 return left
30In 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.
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.
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.