Last Day Where You Can Still Cross — Problem & Solution
Last Day Where You Can Still Cross solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Last Day Where You Can Still Cross is a hard coding problem on arrays, depth-first search and binary search, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Depth-First Search, Binary Search, Matrix, Breadth-First Search, Union Find
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A row x col matrix of land floods one cell per day. On day 0 every cell is land. On day i (1-based) the cell cells[i - 1] = [ri, ci] becomes water — coordinates are 1-based, so [1, 1] is the top-left cell.
You want to walk from any cell of the top row to any cell of the bottom row, stepping only on land and moving up, down, left or right.
Return the last day on which such a walk is still possible.
Example 1
Input: row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
Output: 2
Explanation: After day 2 the right column is still land; on day 3 the top-right cell floods and the top row is all water.
Example 2
Input: row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
Output: 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
Constraints
2 <= row, col <= 2 * 10^44 <= row * col <= 2 * 10^4cells.length == row * col1 <= ri <= row1 <= ci <= colall the values of cells are unique
Hints for Last Day Where You Can Still Cross
Hint 1
If you can cross on day
d, you can cross on every earlier day — fewer cells are flooded. So the answer is a threshold; binary search with a BFS per probe works.Hint 2
Alternatively, run time backwards: start from an all-water grid and turn cells back into land from the last day to the first.
Hint 3
With a union-find plus two virtual nodes (top row, bottom row), the first moment going backwards that they become connected, after restoring
cells[i], means dayiis the last crossable day.
How to solve Last Day Where You Can Still Cross
Flooding only removes land, which breaks connectivity; reversing time turns it into adding land, which only merges components — exactly what union-find does well. Two virtual nodes stand for "the top row" and "the bottom row".
Approach
- Create a union-find over the
row · colcells plus a TOP and a BOTTOM node; start with every cell flooded. - For
ifromrow · col - 1down to 0: turncells[i]into land, union it with TOP if it is in the first row, with BOTTOM if in the last row, and with every neighbouring land cell. - As soon as TOP and BOTTOM share a root, return
i: on dayiexactly the cellscells[i..]are land.
Why it works
On day d the land is exactly cells[d], cells[d+1], …. Restoring cells in reverse order rebuilds those land sets for d = n - 1, n - 2, …, and a top-to-bottom walk exists iff TOP and BOTTOM are in one component. Since crossability is monotone in d, the first d met in this backward scan with a crossing is the largest such day.
Complexity
- Time —
O(row · col · α(row · col)) - Space —
O(row · col)
Pitfalls
- Coordinates in
cellsare 1-based. - Moves are 4-directional; diagonal land does not connect.
- Return the day, not the index of the cell that completed the crossing plus one: restoring
cells[i]gives the land of dayi.
Reference solution
Python
from typing import List
def latestDayToCross(row: int, col: int, cells: List[List[int]]) -> int:
total = row * col
top, bottom = total, total + 1
parent = list(range(total + 2))
land = [False] * total
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
for i in range(total - 1, -1, -1):
r, c = cells[i][0] - 1, cells[i][1] - 1
x = r * col + c
land[x] = True
if r == 0:
union(x, top)
if r == row - 1:
union(x, bottom)
for a, b in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= a < row and 0 <= b < col and land[a * col + b]:
union(x, a * col + b)
if find(top) == find(bottom):
return i
return 0Java
static int[] par;
static int find(int x) {
while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; }
return x;
}
static void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra != rb) par[ra] = rb;
}
public static int latestDayToCross(int row, int col, int[][] cells) {
int total = row * col, top = total, bottom = total + 1;
par = new int[total + 2];
for (int i = 0; i < total + 2; i++) par[i] = i;
boolean[] land = new boolean[total];
int[] DR = {1, -1, 0, 0}, DC = {0, 0, 1, -1};
for (int k = total - 1; k >= 0; k--) {
int r = cells[k][0] - 1, c = cells[k][1] - 1, x = r * col + c;
land[x] = true;
if (r == 0) union(x, top);
if (r == row - 1) union(x, bottom);
for (int d = 0; d < 4; d++) {
int a = r + DR[d], b = c + DC[d];
if (a >= 0 && a < row && b >= 0 && b < col && land[a * col + b]) union(x, a * col + b);
}
if (find(top) == find(bottom)) return k;
}
return 0;
}C++
vector<int> par;
int findRoot(int x) {
while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; }
return x;
}
void unite(int a, int b) {
int ra = findRoot(a), rb = findRoot(b);
if (ra != rb) par[ra] = rb;
}
int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
int total = row * col, top = total, bottom = total + 1;
par.assign(total + 2, 0);
for (int i = 0; i < total + 2; i++) par[i] = i;
vector<char> land(total, 0);
int DR[4] = {1, -1, 0, 0}, DC[4] = {0, 0, 1, -1};
for (int k = total - 1; k >= 0; k--) {
int r = cells[k][0] - 1, c = cells[k][1] - 1, x = r * col + c;
land[x] = 1;
if (r == 0) unite(x, top);
if (r == row - 1) unite(x, bottom);
for (int d = 0; d < 4; d++) {
int a = r + DR[d], b = c + DC[d];
if (a >= 0 && a < row && b >= 0 && b < col && land[a * col + b]) unite(x, a * col + b);
}
if (findRoot(top) == findRoot(bottom)) return k;
}
return 0;
}JavaScript
var latestDayToCross = function(row, col, cells) {
var total = row * col, top = total, bottom = total + 1;
var parent = [], land = [];
for (var i = 0; i < total + 2; i++) { parent.push(i); land.push(false); }
var find = function(x) {
while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
};
var union = function(a, b) {
var ra = find(a), rb = find(b);
if (ra !== rb) parent[ra] = rb;
};
var DR = [1, -1, 0, 0], DC = [0, 0, 1, -1];
for (var k = total - 1; k >= 0; k--) {
var r = cells[k][0] - 1, c = cells[k][1] - 1, x = r * col + c;
land[x] = true;
if (r === 0) union(x, top);
if (r === row - 1) union(x, bottom);
for (var d = 0; d < 4; d++) {
var a = r + DR[d], b = c + DC[d];
if (a >= 0 && a < row && b >= 0 && b < col && land[a * col + b]) union(x, a * col + b);
}
if (find(top) === find(bottom)) return k;
}
return 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Depth-First Search (DFS)