Last Day Where You Can Still Cross

class UnionFind {
    int[] parent, rank;

    public UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
        rank = new int[size];
        Arrays.fill(rank, 1);
    }

    public int find(int node) {
        if (parent[node] != node) {
            parent[node] = find(parent[node]); // path compression
        }
        return parent[node];
    }

    public void merge(int node1, int node2) {
        int root1 = find(node1);
        int root2 = find(node2);
        if (root1 == root2) return;

        if (rank[root1] > rank[root2]) {
            int temp = root1;
            root1 = root2;
            root2 = temp;
        }
        parent[root1] = root2;
        rank[root2] += rank[root1];
    }
}

class PathFinder {
    public int lastPossibleDay(int rowNum, int colNum, int[][] cellPositions) {
        UnionFind uf = new UnionFind(rowNum * colNum + 2);
        int[][] grid = new int[rowNum][colNum];
        int[][] moves = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        
        for (int i = 0; i < rowNum * colNum; ++i) {
            int row = cellPositions[i][0] - 1, col = cellPositions[i][1] - 1;
            grid[row][col] = 1;
            int index1 = row * colNum + col + 1;
            for (int[] move : moves) {
                int newRow = row + move[0], newCol = col + move[1];
                int index2 = newRow * colNum + newCol + 1;
                if (newRow >= 0 && newRow < rowNum && newCol >= 0 && newCol < colNum && grid[newRow][newCol] == 1) {
                    uf.merge(index1, index2);
                }
            }
            if (col == 0) {
                uf.merge(0, index1);
            }
            if (col == colNum - 1) {
                uf.merge(rowNum * colNum + 1, index1);
            }
            if (uf.find(0) == uf.find(rowNum * colNum + 1)) {
                return i;
            }
        }
        return -1;
    }
}

In the given solution, the problem of finding the last day where you can still cross a river represented as a grid is tackled using Java. The solution employs a union-find data structure paired with path compression and union by rank to keep track of connected components efficiently. Below are the key components and steps involved in the solution:

• Define the UnionFind class tailored to manage and merge groups of elements, ensuring efficient operations through path compression and rank-based merging.

• Instantiate the UnionFind to accommodate all potential grid cells plus two extra nodes representing the left and right banks of the river.

• Initialize a matrix (grid) to represent whether each cell is filled or not, assuming all cells are initially empty.

• Monitor cell positions through the cellPositions array, marking them on the provided grid progressively.

• Upon marking a cell as filled, perform union operations for the cell and its neighbors, assuming these are also filled. This ensures that any two connected filled cells are in the same set.

• Specifically treat the top and bottom edges by attempting to union any filled cell at these locations with two additional nodes representing the banks. This aids in determining when a path is completed from the left to the right side.

• Continuously check if the virtual nodes representing the banks are connected. If connected, this indicates a successful path across the river due to the water level, and the current day is returned as the result.

• If, after processing all cell positions, no path across the river is feasible, return -1.

The procedure leverages union-find utilities for efficient merging and path compression, thus enabling rapid checks and operations as the grid configuration evolves. This ensures that the last day where a crossing is possible can be determined efficiently even as conditions change.

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size

    def find_set(self, element):
        if self.parent[element] != element:
            self.parent[element] = self.find_set(self.parent[element])
        return self.parent[element]

    def join(self, element1, element2):
        root1 = self.find_set(element1)
        root2 = self.find_set(element2)
        if root1 == root2:
            return
        
        if self.rank[root1] > self.rank[root2]:
            root1, root2 = root2, root1
        self.parent[root1] = root2
        self.rank[root2] += self.rank[root1]

class Solver:
    def findLastPossibleDay(self, rows: int, columns: int, cellLists: List[List[int]]) -> int:
        uf = UnionFind(rows * columns + 2)
        waterGrid = [[0] * columns for _ in range(rows)]
        movements = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]

        for day in range(rows * columns):
            row, col = cellLists[day][0] - 1, cellLists[day][1] - 1
            waterGrid[row][col] = 1
            currentIdx = row * columns + col + 1
            for dx, dy in movements:
                newRow, newCol = row + dx, col + dy
                neighborIdx = newRow * columns + newCol + 1
                if 0 <= newRow < rows and 0 <= newCol < columns and waterGrid[newRow][newCol] == 1:
                    uf.join(currentIdx, neighborIdx)
                    
            if col == 0:
                uf.join(0, currentIdx)
            if col == columns - 1:
                uf.join(rows * columns + 1, currentIdx)
            if uf.find_set(0) == uf.find_set(rows * columns + 1):
                return day

In the provided Python solution, the goal is to determine the last possible day on which it's feasible to traverse a grid from the topmost row directly to the bottommost row, given new water cells appear daily. The grid itself and the positions of new water cells each day are represented by cellLists.

The implementation uses:

• Union-Find Data Structure: To manage the union and find operations efficiently.
• Grid Settings and Processing:
  • Each cell's water or non-water status is tracked using waterGrid, initialized to mark all cells initially as non-water (0).
  • As water fills cells on subsequent days, union operations connect new water cells to their adjacent water-filled cells.
• Boundary Conditions:
  • If a cell adjacent to the grid's left column becomes water, it's connected to a virtual top node (index 0).
  • Similarly, if a cell adjacent to the grid's right column becomes water, it's connected to a virtual bottom node.

The approach:

1. Initializes the UnionFind for 1-D representation of the 2-D grid, plus two extra indices for the virtual top and bottom nodes.
2. Parses each day’s water-filled cell from cellLists, marks it in waterGrid, and performs union operations with its adjacent already-water cells.
3. After updating connections for a new water-filled cell:
   • Connects boundary cells to respective virtual nodes.
   • Checks if there's a path from the virtual top node to the virtual bottom node using the union-find structure.
4. Returns the day index immediately when such a path is established, indicating the last possible day of traversal before complete disconnection due to water.

The solution efficiently processes the grid and determines the critical day of transition using path compression and union by rank, crucial for handling larger grids with many cells and days. The presence of diagonal movements considered during union operations ensures all possible cell connections are evaluated, allowing a robust and accurate prediction.