Leetcode 1970: Last Day Where You Can Still Cross

Dec 30, 2025

About

The main idea was to check for a “Horizontal River” of connected water tiles that split the top and bottom land rows. I read the hints and saw that DFS with binary search for the days was also an option, but I really wanted to mix UnionFind with the horizontal river idea. It’s extremely messy but shockingly works for tonight.

Other notes that the river could consist of a completely horizontal line of water tiles, or include many diagonal cell connections. This is why unionFind is needed, and I can’t just check each row for a straight line of water tiles.

My first thought was to unionFind together all the starting land cells, then cut connections between them as water tiles are added. Instead, treating water tiles as unionFind connected components was a much easier thought process. Instead of having to constantly rerun DFS/BFS from top row cells to bottom row tiles, I could just check for this “horizontal river” of water tiles instead. Surprisingly, I didn’t even need to binary search through the “cells” coordinate array; I passed the LeetCode judge using only my UnionFind-based solution.

Solution

Uses Union find, with a custom method named floodCell. Also added a custom array this.flood for tracking the boolean status of whether a given cell is land or water. Also, instead of a traditional rank array for path compression/find optimization, I made this into a messy “unique column” tracking sets.

The thought is that if my number of unique columns for a connected water tile grouping is equal to the total number of columns in my pretend matrix, then I have formed a full-length horizontal river of water tiles.

The floodCell method sets this.flood with water/land status, updates “rank sets” with the new unique column values for the given connected water group, then, for the day’s event coordinates, checks around for fellow flooded neighbors.

If the neighbors are already flooded, then it unions them together and updates the neighbors’ unique column set ranking as well.

At the end, floodCell returns true if the act of watering the current day tile creates a full-length horizontal river bisecting the top and bottom row, otherwise returns false/

TLDR

Wasted so much time on UnionFind, this hard daily problem. Also wrote when sleepy, oof.

/**
 * @param {number} row
 * @param {number} col
 * @param {number[][]} cells
 * @return {number}
 */
var latestDayToCross = function(row, col, cells) {
    class UnionFind{
        constructor(){
            this.parent = _.range(0,row*col+1 );
            this.flood = new Array( row*col+1 ).fill(0);
            this.rank = Array.from( {length: row*col+1}, ()=>new Set() )
        }
        find(A){
            let root = this.parent[A];
            if(this.parent[root] !== root){
                return this.parent[A] = this.find(root);
            }
            return root;
        }
        union(A,B){
            const a = this.find(A);
            const b = this.find(B);

            if(a === b){ return; }

            if(this.rank[a].size < this.rank[b].size){
                this.parent[a] = b;
                this.rank[b] = this.rank[a].union(this.rank[b]);
            }else {
                this.parent[b] = a;
                this.rank[a] = this.rank[b].union(this.rank[a]);
            }
        }
        floodCell(R,C){
            this.flood[R*col + C] = 1;

            let ROOT = this.find(R*col+C);
            this.rank[ROOT].add( C );

            for(let RR = R-1; RR< R+2; RR++){
                for(let CC = C-1; CC< C+2; CC++){
                    if(RR >= 0 && CC >= 0
                    && RR < row && CC < col){
                        if(this.flood[RR*col + CC] ){
                            this.union( R*col+C, RR*col+CC);
                            ROOT = this.find(R*col+C);
                            this.rank[ROOT].add( CC );
                            if( this.rank[ROOT].size == col){
                                return true;
                            }
                        }
                    }
                }
            }
            return false;
        }
    }

    let myUF = new UnionFind();
    let I = 1;
    for(let [R,C] of cells){
        R = R-1; C = C-1;
        if( myUF.floodCell(R,C) ){
            return I-1;
        }
        I++;
    }
};