# 31.12.2025 [1970. Last Day Where You Can Still Cross]
Last day top connected to bottom in 2D matrix #hard #uf
31.12.2025
1970. Last Day Where You Can Still Cross hard blog post substack youtube
Join me on Telegram
Problem TLDR
Last day top connected to bottom in 2D matrix #hard #uf
Intuition
Invert the problem: go from back and the list becames a “rain of the ground cells”.
Approach
we can store ground bits inside union-find jump array as an extra bit
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(n)$$
Code
// 68ms
val u=IntArray(21000){it*2}; fun f(a:Int):Int=if(u[a]/2==a)a else f(u[a]/2).also{u[a]=it*2+u[a]%2}
fun latestDayToCross(r: Int, c: Int, cs: Array<IntArray>) = (cs.lastIndex downTo 0).first { i ->
val (y,x)=cs[i]; val s = 1+2*f(if(y==1)0 else if(y==r)2 else y*c+x); u[y*c+x]=s
for ((x1,y1) in arrayOf(x-1 to y, x+1 to y, x to y-1, x to y+1))
if (y1 in 1..r && x1 in 1..c && u[y1*c+x1]%2>0) u[f(y1*c+x1)] = s
f(0) == f(2)
}
// 14ms
pub fn latest_day_to_cross(r: i32, c: i32, cs: Vec<Vec<i32>>) -> i32 {
let (r, c) = (r as usize, c as usize); let mut u: Vec<_> = (0..r*c+c+1).map(|i| i * 2).collect();
fn f(u: &mut Vec<usize>, a: usize)->usize{if u[a]/2==a{a}else{let t=f(u,u[a]/2);u[a]=t*2+u[a]%2;t}}
(0..cs.len()).rev().find(|&i| {
let (y, x) = (cs[i][0] as usize, cs[i][1] as usize);
let s = 1+2*f(&mut u,if y==1 {0} else if y == r {2} else {y * c + x}); u[y * c + x] = s;
for (dx, dy) in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)] {
if dy >= 1 && dy <= r && dx >= 1 && dx <= c && u[dy * c + dx] % 2 > 0
{ let r = f(&mut u, dy * c + dx); u[r] = s }}
f(&mut u, 0) == f(&mut u, 2)
}).map(|i| i as i32).unwrap_or(-1)
}