1970. Last Day Where You Can Still Cross
Asked at Atlassian
Difficulty
Hard
Time
O(row * col * log(row * col))
Space
O(row * col)
Pattern
Array
Companies
1
Problem
You have a grid with row rows and col columns. On day 0 the whole grid is land. Then, one cell per day turns into water. The list cells tells you the order: cells[i] = [r, c] means that on day i+1 the cell at row r, column c becomes water. Coordinates in cells are 1-based.
You want to walk from the top row to the bottom row using only land cells. You may start at any cell in the top row and finish at any cell in the bottom row. Each step moves up, down, left or right to a neighbouring land cell.
Return the last day on which such a top-to-bottom walk is still possible. Note that day 0 always works, because the grid is fully land. Once crossing becomes impossible, it stays impossible forever, since cells only turn into water and never back into land.
Flooding over the days
Constraints
- ●
2 <= row, col <= 2 * 10^4 - ●
4 <= row * col <= 2 * 10^4 - ●
cells.length == row * col - ●
1 <= ri <= row - ●
1 <= ci <= col - ●
All values in cells are unique
Examples
row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]2row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]1row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]3Asked At
1 companies| 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.
Binary search on the day
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
O(row * col * log(row * col)) timefrom 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 runs in O(row * col * log(row * col)) time and O(row * col) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.