Last Day Where You Can Still Cross

Problem Statement

In this problem, you are dealing with a dynamically changing environment represented by a 1-based binary matrix, where the integer 0 represents land and 1 represents water. The matrix dimensions are provided by the integers row and col for rows and columns respectively. At the beginning (day 0), the matrix starts entirely filled with land (0s).

Each subsequent day, the matrix undergoes a change where a specific cell, previously land, is converted to water (1). This transition is directed by a given 2D array cells, in which each element cells[i] = [ri, ci] marks the cell at row ri and column ci to be flooded on the ith day.

The crux of the problem is to find out the last possible day on which it remains feasible to traverse from any cell in the topmost row to any cell in the bottom row by only walking on the cells still marked as land. The permissible movements from any cell include only the four cardinal directions—up, down, left, and right.

The goal is to determine the last day after which such a traversal from top to bottom is completely obstructed by water.

Examples

Example 1

Input:

row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]

Output:

2

Explanation:

The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 2.

Example 2

Input:

row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]

Output:

1

Explanation:

The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 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

Explanation:

The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 3.

Constraints

• 2 <= row, col <= 2 * 104
• 4 <= row * col <= 2 * 104
• cells.length == row * col
• 1 <= ri <= row
• 1 <= ci <= col
• All the values of cells are unique.

Approach and Intuition

To tackle this challenge, let's break down the process into manageable components:

1. Initialization: Initially, all cells are set as land (0s).
2. Sequential Flooding: Using the cells array, which dictates the order in which cells are converted into water. Every day, a specific cell denoted by cells[i] turns into water.
3. Connectivity checking: After each transformation (daily flooding), check whether there is still a viable path that connects the top row to the bottom row traversing only land cells. This requires an effective method to check connectivity in potentially large grids.
4. Binary Search for Efficiency: To optimize, consider using binary search. The binary search can be applied over the days to quickly hone in on the last day where a path exists. This will significantly reduce the number of connectivity checks needed as compared to iterating day-by-day.
5. Graph Theory and Union-Find: Utilize graph algorithms or a union-find (disjoint set) data structure to manage and query connectivity between the top and the bottom of the matrix efficiently. Union-Find is particularly useful here to dynamically manage connected components of the land cells as they increasingly turn into water.
6. Stopping Criteria:
   • If you find a day where you can no longer traverse from top to bottom, then the day before that is your answer.
   • Iterate until all days in the cells array are exhausted, ensuring that every flooding event is accounted for.

This systematic approach ensures that you are computing the required day efficiently while correctly handling the dynamic nature of the problem.

Solutions

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;
    }
}