Last Day Where You Can Still Cross
Asked at Atlassian
Problem
You are given a m x n binary matrix grid where 1 represents land and 0 represents water. Each day cells flood from the top row to the bottom row. Return the last day where you can still walk from the top row to the bottom row by moving to adjacent un-flooded cells.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | HARD | View all Atlassian questions → |
How to Think About It
Brute force: simulate flooding day by day and check connectivity each time using BFS or DFS.
Binary search on the answer: the property "can cross" is monotonic (once false, stays false).
For a given day, mark all cells flooded up to that day and run BFS/DFS from all top-row dry cells.
Union-Find is an alternative: union adjacent dry cells and check if any top-row cell connects to any bottom-row cell.
Optimal: binary search over [0, mn] days with BFS connectivity check per mid value, giving O(mnlog(mn)).
Optimal Approach
Binary search on the number of days. For each candidate day, construct the grid state by marking cells flooded up to that day as 0, then run BFS from every un-flooded top-row cell to see if any path reaches the bottom row. The monotonic property ensures binary search is valid: if crossing is possible on day d, it is possible on all days before d. BFS runs in O(mn) per check, and binary search adds a log(mn) factor, yielding O(mnlog(m*n)) overall.
What Trips People Up in Real Interviews
Clarify whether the grid is 0-indexed and whether diagonal movement is allowed (it is not in this problem).
Recognize the monotonic property early: if you can cross on day d, you can also cross on any day before d.
When using BFS, seed the queue with all un-flooded cells in the top row rather than checking each one separately.
With Union-Find, process cells in reverse (from last flood day back to first) so you union dry cells as they reappear.
Edge case: if m or n is 1, the answer may be 0 or m*n-1 depending on the initial grid state.
Solution Code
from collections import deque
def latestDayToCross(row, col, cells):
grid = [[1] * col for _ in range(row)]
left, right = 0, len(cells) - 1
result = 0
def can_cross(day):
for i in range(day):
r, c = cells[i][0] - 1, cells[i][1] - 1
grid[r][c] = 0
queue = deque()
for c in range(col):
if grid[0][c] == 1:
queue.append((0, c))
visited = set()
while queue:
r, c = queue.popleft()
if r == row - 1:
return True
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < row and 0 <= nc < col and grid[nr][nc] == 1 and (nr, nc) not in visited:
visited.add((nr, nc))
queue.append((nr, nc))
return False
while left <= right:
mid = (left + right) // 2
for i in range(row):
for j in range(col):
grid[i][j] = 1
if can_cross(mid):
result = mid
left = mid + 1
else:
right = mid - 1
return resultFrequently Asked Questions
What is the Last Day Where You Can Still Cross problem?
You are given a m x n binary matrix grid where 1 represents land and 0 represents water. Each day cells flood from the top row to the bottom row. Return the last day where you can still walk from the top row to the bottom row by moving to adjacent un-flooded cells.
How do you solve Last Day Where You Can Still Cross?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Last Day Where You Can Still Cross?
Last Day Where You Can Still Cross is asked at Atlassian. It is a hard difficulty problem.
What are common mistakes on Last Day Where You Can Still Cross?
- Clarify whether the grid is 0-indexed and whether diagonal movement is allowed (it is not in this problem).
- Recognize the monotonic property early: if you can cross on day d, you can also cross on any day before d.
- When using BFS, seed the queue with all un-flooded cells in the top row rather than checking each one separately.
- With Union-Find, process cells in reverse (from last flood day back to first) so you union dry cells as they reappear.
- Edge case: if m or n is 1, the answer may be 0 or m*n-1 depending on the initial grid state.